Have a single, universal national ID. Issue it for free, or for a low fee ($5). Have town halls issue it to everyone.
How hard can it be? Almost every country in the world has it: https://en.wikipedia.org/wiki/Identity_document
"In many countries – especially English-speaking countries such as Australia, Canada, Ireland, New Zealand, the United Kingdom, and the United States – there are no government-issued compulsory identity cards for all citizens."
So yes, everyone else has it. And it's not like everything else is a nightmare dystopia...
https://en.wikipedia.org/wiki/Common_law#/media/File:Map_of_...
I have never heard anyone suggest we need a national ID in New Zealand.
And "many" countries is basically the 10 or so English/British-derived countries. Look at the list I linked :-)
As an American who has lived all over the country, i'd say every American subculture has a strange relationship with our government. The prospect of nationalizing, much less requiring, anything causes some cohort of the public to complain of government overreach or the trampling of liberties or that they didn't go far enough.
There is an argument to be made for whether or not a national id constitutes any real harm, and i'm sure our hesitation seems foolish to people in other nations. For me, i consider it to be a healthy, if inefficient, debate. Our government moves very slowly with this stuff. Depending on your personal beliefs, you can thank/blame the general public for that.