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.