You shouldn't try to share them, imo, and generate a key for each device. Yes, that may be painful to have to copy 5 public keys on each new server, but the day where, say, your laptop get stolen, you don't have to change the private key on each device : simply remove the laptop one.
If you want some kind of centralization, you could only add your keys on a single server, then add this server key on others. You log on first server, then use it to log on others. But that would be dangerous : if the master server crashes, you can't access other servers anymore. Redundancy is good, in that case.
I agree that key-for-each-device is probably best practice.
It just doesn't work for me though. I frequently need to log onto servers from new client computers, and the workflow of connect from trusted device, generate new key for new device then use new device just isn't practical.
I've spent a lot of time thinking about this.
I think the biggest threat to security on my servers is brute forcing of ssh passwords. The best solution for that is key based authentication. (I deploy fail2ban as well though)
There is a non-zero threat of my devices being lost/stolen/accessed with my keys on them.
So key based authentication is the way to go, but I just can't get around the practical aspects.
In the end I often rely on long, random passwords kept in a KeePass database I sync (along with Fail2Ban). I've considered keeping my private keys in that too, and to be honest I think that isn't a terrible solution. It is certainly less than ideal, but probably mildly more secure than my current method (ie: really a private key shared across devices is acting as a very long password)
"I frequently need to log onto servers from new client computers, and the workflow of connect from trusted device, generate new key for new device then use new device just isn't practical."
Agree. But wouldn't it make sense then to generate unique keys for all of your devices (still) and then have a key which is your "travel" key and change that periodically?
I keep my travel key in a pen drive, and in practice I change it shortly after every usage. But that's because I don't use it a lot, you'll probably want to change it every few weeks.
Also, if you don't trust the machines you are using to connect, no time frame is small enough. If you really need to connect from them, use a VM (best) or a guest account (not as good) with access to just the stuff you need.
Your private key should be encrypted with a strong password.
If you follow that best practice, you can stop worrying about your laptop being stolen, and start worrying about five dollar wrenches. (http://xkcd.com/538/)
Better way to reduce the need for copying keys around would be setting up a private CA, and signing the individual keys with it. Of course you need to keep the CA key secure, I'd strongly suggest removable media or preferably a real HSM.
If you want some kind of centralization, you could only add your keys on a single server, then add this server key on others. You log on first server, then use it to log on others. But that would be dangerous : if the master server crashes, you can't access other servers anymore. Redundancy is good, in that case.