It is quite straightforward to upgrade SSN system. Social Security Administration can generate deterministic Private+Public key pairs for all citizens.
Public key is your new SSN. If it gets stolen, simply generate a new public key, and give it out as a new number. All public keys are easily verified since SSA knows the private keys.