What makes it even worse is that the SSA makes it virtually impossible obtain a new SSN. Even showing them that you were a victim in a high profile leak like this, for example, isn't enough. You have to prove actual misuse, such as someone taking a credit card out or being arrested in your name, before they will issue a new one. In almost all cases, police reports are required.
Given that a new SSN is essentially impossible, if I were a victim in this, I would immediately freeze my credit file at all 3 major credit bureaus. In most states this can be done for $0-$10 per bureau. This can cause hassles for instant credit approvals etc, but they provide mechanisms to unfreeze the file temporarily when necessary.