The passphrase that can be set on the private key is unrelated to the SSH server or the connection to it. Setting a passphrase to the private key is merely a security measure the key owner may take in order to prevent access to his remote shell by a third party in case the private key gets stolen.
Unfortunately, you cannot force users to secure their private keys with passphrases. Sometimes, unprotected private keys are required in order to automate access to the remote SSH server. One good habit I highly recommend for such cases is to advise the users to hash the known_hosts file (stored at ~/.ssh/known_hosts), which keeps information about the remote hosts the user connects to, using the following command:
ssh-keygen -H -f ~/.ssh/known_hosts
This way, even if a third party gained access to an unprotected private key, it would be extremely difficult to find out for which remote hosts this key is valid. Of course, clearing the shell history is mandatory for this technique to be of any value.
Also, another thing you should always bear in mind, is not allow root to login remotely by adding the following in your SSH server's configuration (sshd_config):
PermitRootLogin no
On the other hand, if you want to prevent users from using keys to authenticate, but instead use passwords, you should add the following to your sshd_config:
PasswordAuthentication yes
PubkeyAuthentication no
There are plenty of ways of doing this. LDAP key storage has been mentioned a couple of times, and I've done that and it works, as far as it does. LDAP has it's own management curiosities, though, which take some learninating.
I'm a big fan of simple, robust servers that have minimal external network dependencies for simple things like authenticating administrators, so I lean towards a far more robust SSH key distribution strategy -- I have the configuration management system take care of it. Everyone's public key is kept in the configuration management system, and wherever the person needs to be able to login, their key is added. The config system also knows to remove keys that aren't specified, so when someone leaves or their key changes, it's a simple matter of removing the key configuration and on the next config system run, the key is removed.
Best Answer
Yes, Puppet is the right way to do this, and from that other question, Option 3 seem to be the most sensible (as well as being the accepted answer [always a good sign!]).
There's a ssh_key module for puppet which makes the whole thing trivially easy.