You have to make important distinctions: there are public keys and private keys. When "stored securely", they call for different notions of "securely".
Each SSH server owns a public/private key pair. Each server should generate its own key pair, and the private key should never leave the server itself. The public key is public, meaning that everybody can learn it. When you connect to the server, that's one of the first things that the server tells you: its public key. It shouts it all over the network. When dealing with SSH public keys and their storage, the question is really that of integrity: a given SSH client must remember the public keys of all the servers that it wants to talk to (the
$HOME/.ssh/known_hosts file with usual Linux SSH clients); the attacker may want to include a fake public key in there, in order to run a fake server.
Each SSH client may own a public/private key pair: such a key pair will be used for client authentication by the server. If you use password-based client authentication, then the clients don't have such key pairs. If you use key-based client authentication, then each server must know the public keys of "authorized clients" (the
$HOME/.ssh/authorized_keys for Linux SSH implementations).
In your case, you have 50 SSH clients talking to 4000 SSH servers. Therefore, using the normal SSH model, you would have to ensure that:
- Each of the 50 clients knows a copy of the public keys for all 4000 servers.
- If using key-based client authentication, each of the 4000 servers must know a copy of the 50 client public keys.
Given these figures, the relevant files will be bulky, and key management will be a problem (if you add a new client, the new client's public key must be imported into 4000 servers, with protected integrity). Public-Key Infrastructures were invented to solve that problem. A raw, "official" OpenSSH instance does not know how to use X.509 certificates; however, a modified version exists (see also that previous question). With an X.509-aware SSH code base, you could run your own Certification Authority (e.g. the open-source EJBCA), and issue certificates for your clients and servers. That way, SSH client and servers will send each other their certificates when needed, dynamically. Each machine will only have to store its own private key and certificate, and also "know" the CA certificate (in the relevant "trust store"). Adding a new client or a new server to the mix then is just issuing a certificate, and the management problem is solved (or, rather, moved around: now you have a PKI to handle).