When you want to have public key based ssh logins for multiple machines, do you use one private key, and put the same public key on all of the machines? Or do you have one private/public key pair for each connection?
I use one key per set of systems that share a common administrative boundary. This limits the number of machines that get popped if a key is compromised, whilst not completely overwhelming my capacity to store and manage several thousand keys. Different passphrases on each key means that even if all your private keys are stolen and one key is compromised, the rest don't go down the toilet with it. Also, if you do do something stupid (like copy a private key onto an untrusted machine), again you don't have to rekey everything, just the machines associated with that key.
The public key doesn't matter much, since, by definition, it can be publicised. So the only issue is the privacy of your private keys. They're on your own machine, and all together, so if one is compromised, it's likely that they'll all be compromised. Therefore, multiple keypairs is just more work for the same effect.
The only time I would use different keys is for different accounts or different roles, which by definition shouldn't have complete overlap in access.
If I understand properly, each server is going to have its own public key.
For a given user, you can generate one key and use it everywhere, so long as the private key is replicated across to all initiating hosts. (This would happen automatically via network-mounted home directories and a directory-based authentication system such as OpenLDAP since the user will always be "the same" regardless of what workstation they login from.)
Outside of a directory-based user system, I think it's a Bad Idea™ to use the same keys everywhere - you end up with a net reduction in system security, as anyone who can get a key from any of the workstations can then authenticate as that user to the remote server.
Another alternative, emplyed by several large corporations (and I'm sure small ones, too) is to never allow a "user" to use pre-shared keys, but rather to have then login to a "jump" or "hub" box,
su to the appropriate connecting user, and then SSH from there to the servers they need to manage.
Also, if you use a management system like HP's Server Automation platform, then remote administration of managed servers becomes a more simplified process.
As others have said, although the idea of multiple key pairs may seem more secure, if there is a chance they will be used in such a way that they are all in the same place then it is just more hassle and not more secure. Multiple passphrases would make it more secure but also a big headache trying to remember which passphrase goes with which key, and which key goes with which server.
The most reasonable answer to me would be the one where it was suggested doing that ONLY if it involves separate administrative roles without much overlap. Such that it could be different people handling the different roles, or on different workstations or whatever. In that case you have more unique things to deal with for each different role anyways so it's more justifiable.
For ease of managing multiple SSH capable servers, you may want to check out cssh. You can combine cssh with passphrased SSH keys to greatly enhance your ability to manage multiple servers simultaneously.