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.