One approach I've heard of, but not used myself, is for each user to have a package (eg, .deb, .rpm) which contains their ssh public key config, as well as any dotfiles they like to customise (.bashrc, .profile, .vimrc etc). This is signed and stored in a company repository. This package could also be responsible for creating the user account, or it could supplement something else creating the account (cfengine/puppet etc) or a central auth system like LDAP.
These packages are then installed onto hosts via whatever mechanism you prefer (cfengine/puppet etc, cron job). One approach is to have a metapackage which has a dependency on the per-user packages.
If you want to remove a public key, but not the user, then the per-user package is updated. If you want to remove a user, you remove the package.
If you have heterogeneous systems and have to maintain both .rpm and .deb files, then I can see this being a bit annoying, although tools like alien might make that somewhat easier.
Like I say, I've not done this myself. The benefit in this approach to me is that it supplements a central LDAP system and central management of user accounts, in that it allows a user to easily update his package to include his .vimrc file, for example, without having to have that file managed by tools like puppet, which a user may not have access to.
Follow-up question: you use cfengine to distribute .authorized_keys. Did you look into any of the ways to store SSH public keys in your LDAP server directly? They mostly require patching sshd, which feels fragile.
– Evan Prodromou Jan 23 '13 at 18:55ProxyCommand ssh -qbit there! Never seen that. I'm hesitant to put up a bastion server but if it can be transparent to the end users then I might be all for it. Thanks Martin! – Randy L Aug 07 '16 at 18:58