What is the best approach for RSA key management on Ubuntu?

We manage all our key using Puppet. Each key has a comment identifying the employee by name, and when someone loses theirs, or they leave, or whatever, we just update the manifest and Puppet takes care of clearing out the old and adding the new.

I understand you very well. When I implemented RSA authentication to access our servers just for the developers I got a really nasty days. In fact most of ordinary users still hate me for "very cryptic passwords". I can't make this work right at once, but maybe some regular notes on security will give some results and users will understand why this is needed.

You cannot do much on the users' computers. Actually, if you have administrative rights on the office computers you'll be able to perform some checks for default SSH keys paths, check running ssh-agents, key passwords, reading .ssh/config to gather additional info. But if the key is stored somewhere else, you won't be able to do much.

It was told somewhere that you should trust but check in this situation. This mostly means that you can just check sometimes how the user is accessing the server and consult him why it's necessary to use a password to secure private key, etc.

As for the server part, I'm storing all users' public keys in the LDAP database and am using patched SSH server to get public keys from LDAP. The patch is called LPK, and is not hadr to configure along with LDAP PAM authentication/authorisation. It's home page is http://code.google.com/p/openssh-lpk/. I just rebuild the debian package with this patch (sometimes a bit modifying it to fit well) and store into our company's local repositroy which has high priority. LDAP is available to store multiple user's keys and if some key is compromised or lost I just remove its public part from the LDAP server.