I said it before, I say it again, a change of keys IS POSSIBLE and yes, it could be used to tighten up the security again. However, it is not trivial.
a) Add a second public key to the PS3.
b) Use the private key for the new public key to sign new games.
c) Create a checksum list of the headers of all old games - PSN games could be updated for the new keys I guess.
d) Once the checksum list is complete - remove the original public key.
The new public key would not allow exposal of the private key, if Sony did use a really random number to hide their private key. That system is used by the DSi, however, such a system is flawed as R4i and all other DSi flash cards show - they simulate the header of a known game, the DSi verifies the header and on load the header data is replaced with the actual flashcard header- at that time the DSi already accepted the flash card as valid! Something like that could happen on the PS3 then, so that would raise the security of the system again, however it makes exploits to the verification very possible!