One point in favor of requiring ssh keys for external access is that the users don't get to blow it on passwords. Though it does require sysadmin staff who are willing to walk users through the process of creating the keys --- and stubborn enough to explain that this is the procedure until following it becomes the path of least resistance.
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.
