SSH private keys should never leave the machine they were generated on, unless to be moved into a more secure platform, such as an HSM. Likewise, they should never be accessible to anyone other than the person who generated them and will be using them, e.g. an administrator's workstation, or better, an HSM/smartcard. If you're going to be accessing a server from multiple machines, generate a unique key on each machine and deploy the public keys accordingly, or put a public key from a smart card or other strong authenticator into the authorized keys.
For starters, I always recommend protecting private keys with a passphrase. This will mitigate the chances of unauthorized key usage if it falls into the wrong hands. A higher security measure is to embed the private key into a smartcard, and make use of the cryptographic functions on it via a middleware. Redhat makes it easy to do all this.
How do you protect your private ssh keys? I read about ssh-agent but I
am not sure how to use it or if it can be used in this situation.
ssh-agent is used in a terminal session, to cache the unencrypted version of the private key, making it unnecessary for you to enter the key's passphrase each time it is used. You can also use an external authenticator by which you make use of an authentication challenge/response, but never have access to the cleartext. Please take a peek at http://www.gooze.eu/howto/using-openssh-with-smartcards/using-ssh-authentication-agent-ssh-add-with-smartcards in order to review how you can use ssh with a secure authenticator.
If a sysadmin leaves and he copies all the private ssh keys, then he
has access to all the servers. How do you deal with this situation?
This is a very strong argument as to why private keys should never be shared, and certainly why multiple users' keys should never be stored together. Plain and simple, there is no reason to do so. No one else has any business getting your private key. That said, even if you were in a situation where someone got their hands on a bunch of active private keys, if they were properly passphrase-protected by a strong passphrase, it would largely be a non-issue.
Again, by credentialing your users with a strong authenticator having cryptographic functions, you can avoid this situation altogether. When a machine needs to perform cryptographic functions, rather than store a private key on the filesystem, you can store it on an HSM to prevent exfiltration (theft) of the private keys.
SSH keys private keys can be a component of multi-factor authentication system, such as a smart card, or another type of hardware security module (USB form factor, PCIe card, fortezza, networked HSM, etc) This is pretty standard now for security conscious businesses, governments and the military operate simply because one compromise can lead to massive exposure; passwords are too weak.
A smart card, depending on the security of it, can be either (A) unvalidated, a (B) FIPS 140-2 level 2 device, all the way up to a (C) controlled cryptographic device usable for Top Secret SCI information and Suite B algorithms. In the case of (B), a government authorized lab has independently validated the cryptography, and (C), the NSA has evaluated the device in question. B is considered equivalent to best commercial grade security, and C is considered military / intelligence community grade. Prices go up for the robust stuff!
