Key pairs should be generated by the user.
The user retains the private half - you should never see it. If you have someone's private key in a form where you can read/use it you're doing security wrong.
The public half is given to you (by whatever mechanism you'd like: Web form, email, give-it-to-me-on-a-CD), to be centralized however you want. Some places store the public keys in LDAP. Others push out
authorized_keys files using their deployment system.
In my environment users who need shell access give me their public keys. These keys are added to our LDAP system, and
sshd consults the public key(s) listed for each user to authenticate them, by way of the LDAP Public Key patch.
When someone needs to add an additional key or revoke an existing key they let an admin know, and we take care of it. Eventually as we scale I will implement a system that lets people rotate their own public keys.
Each of our sites has a pair of LDAP servers, synchronized to our master with LDAP replication, which keeps the data consistent (and accessible) at each location.
Everything I have described can be done with open-source software. There are also commercial products that do the same thing.
You need to research the available options more thoroughly and decide which one(s) suit your environment best. If you have further (more specific) questions we can probably be more helpful.