I agree with you. Switching to another id system will mean we use that instead of SSN and have the same potential issues. I think the biggest problem here is our approach to credit and credit fraud. We need mandatory CC2 online, mandatory 2FA (not SMS!), chip and PIN, our credit should be frozen by default with out of band approval for new credit and credit granted without approval is the lender's responsibility. Steps like these would remove most of our exposure to credit fraud.

The government could bring in an auth service adding a password to your SSN. Problem solved. Kinda.

or a digital signature, or a MAC. Something where we could verify against a publicly-known value safely, and without giving that secret part away to anyone else. The secret would be between the Federal Government and the citizen.

Why should the government have it at all? Just let private citizens manage their own private key.

And what happens when people inevitably lose their private key? How will they regain access to their SSN?

They would probably have to through a similar procedure as they do to get a replacement social security card. That is, they would have to present at least a drivers license and US passport at one of the local social security administration offices.

At that point, they can regenerate the key-pair and have the SSA official sign the public key and keep that on file.

Now, presumably, it is possible to forge both documents, but I would think that the government could check their records (federal and state) to verify the authenticity of the provided documentation.

Exactly. You can't have perfect trust in every citizen to keep track of these things. And if it's a government issued ID in the first place, I see no trouble with them having your private key as well. Just don't reuse that key.

This would take a lot of solid investment politically, and technically, to make it even slightly feasible to work for the average Joe.

Couldn't we do this thorugh a system that's similar to PKI? That is, have each person generate a private-key and certificate signing request (that's signed by the appropriate government agency)?

Resetting it outside the normal certificate expiration time would require that one go to the local branch of the government office to do so (much like getting a replacement social security card or replacing a lost or stolen passport). At that point, you would have to provide proof of your identify that would be verified by the government agency.