Rather than being about fast/simple/cheap, I think using SSN as a key was more about the fact that SSN is the only common identifier that almost all US citizens have.

I think you're using the word "key" differently than OP. You're talking about identifiers, and they're talking about security.

SSNs were a good potential identifier, until the people that needed security cheaped out and started using SSNs as a bad implementation of security. Now they're bad at both purposes!

Yes, designing and implementing a new common identifier almost all US citizens have would have been less cheap and fast.