Problems with PGP/SSH-key not being changable the way a password is

Question

I've started using key-based encryption and authentication about three months ago. As most people getting started with something, I did not know all the fine details of usage and secrecy of private keys. As a result, I did not keep proper track of where I put the keys.

I think I may or may not have used insecure means to transfer my private key to a couple of my machines. So technically speaking, Google could have my private key stored somewhere in their evil all-knowing data-gathering fortresses of doom.

I'm not worried about my key having been compromised, I do think I've taken enough care to make sure that did not happen. But would this have happened with a password, I do think I'd have changed it.

That got me thinking. Private keys are used to authenticate, encode and decode a lot of information. Isn't this a weak point? What if I did accidentally spill my private key somewhere? Anybody would be able to decrypt all messages I've ever encoded, and access all servers I could. Opposed to this, if I accidentally spill a password, I just change it. Keys, not so much.

In addition:

Treat your password like a toothbrush - don't let anybody else use it, and get a new one every six months. — Clifford Stoll

This isn't really possible with a private key (unless I'm terribly mistaken). Isn't this a security concern too?

Isn't in this case a good password (32 characters, a-Z/0-9/~!@#$ etc) stored somewhere secure better?

Answer 1

Of course you change keys, you just have to find all the places that accept them, and change which ones are accepted. Edit the authorized_keys files in case of an SSH server. Requires logging in to all the machines, but it's exactly the same if you want to change your password.

If you have, say, files encrypted to a GPG key and you've misplaced them, in addition to the key, then it's a bit more annoying, since you need to find and delete or change all the files too. Any GPG-encrypted emails sent to your old key would still be readable by someone who the key was leaked, if they can get their hands on your old emails. But this isn't any different from passwords either. If you have files encrypted to a password, anyone with the file and the password can read it.

Anybody would be able to decrypt all messages I've ever encoded, and access all servers I could.

I think this would apply completely even with the precondition changed to "what if I accidentally spill my password".