If you don't want to pay or go the hassle of a credit freeze you can file a fraud alert with the credit bureaus. It is free but it only lasts for 90 days. It does roughly the same as a credit freeze. I keep resubmitting about every 90 days. Supposedly, if you file a fraud alert with one, they send it to the other two automatically.
As to the NSA, they don't really need to keep our info as there are other public companies that compile info. Companies like Lexis Nexus or Reed Elsevier did it at one time. They may still do but not publicly advertise it. They compile all public records, marriage/divorce certificates, real estate transactions, child births, car accidents, arrest, convictions, insurance claims, where you work, where you lived, phone numbers, ... An unworldly amount of personal data. While they (supposedly) don't keep credit records as such, they could probably back engineer them if needed. I'm sure if the NSA wanted that data they could get it easily or perhaps have a back door into those databases.