Your options are basically to either force everyone to use short keys that can be brute forced by the NSA (and anyone with cash to throw at AWS) or to set up a trusted-third party to store everyone's private keys and then either enforce long key lives or come up with a mechanism to transport the keys to the third party as old ones expire.
Weakening encryption would lead to massive issues for both corporate and personal security. What's worse is there wouldn't be anything stopping anyone from rolling their own crypto without the NSA's permission (it's literally just math), so it'd be business as usual for terrorists and black-hats.