Also, passwords are compromised much more often than keys. To get someone's SSH key you have to have access to their local workstation, which is probably going to be more troublesome than access to a colo'd server, if for no other reason than most workstations go to sleep after they've been inactive for a while (there are other reasons, though).

Also, changing keys isn't that hard. You just re-run ssh-keygen and delete the old key from authorized_keys and replace it with the new one.

replacing the private key is the hard part. it's the kind of thing where you don't discover that the new private key for your server isn't on your backup laptop until you need to login and don't have access to a system with they key.