Here is the solution from the link I posted in my comment. This comes from here, which references this superuser post.
Create .ssh folder in /home for the keys to be stored
sudo mkdir /home/.ssh
Move existing authorized_keys file into .ssh dir as username
sudo mv ~/.ssh/authorized_keys /home/.ssh/username
Create symbolic link to authorized_keys file in user .ssh dir
ln -s /home/.ssh/username ~/.ssh/authorized_keys
Update sshd_config file to set the new path for the authorized_keys file
sudo vim /etc/ssh/sshd_config
Change the AuthorizedKeysFile line to:
AuthorizedKeysFile /home/.ssh/%u
Reboot the computer
sudo shutdown -r now
Login to your server and you should be presented with a minimal un-decrypted home directory... You will need to create and edit a .profile file in there to get ecryptfs to mount your home directory.
sudo vim ~/.profile
Add these lines:
ecryptfs-mount-private
cd /home/username
Log out/Restart, and go back in again. You should be prompted for your password after SSH key auth, and then be presented with your decrypted home directory.
You should now be able to login using SSH keys every time, no matter if your home dir is decrypted or not.
There are a bunch of ways to do this, especially if you're on recent versions of OpenSSH. Remember also that you need more than a way to add them, you need a way to remove them (and quickly—consider if the key is compromised, the person parts on bad terms, etc.). A key addition that takes a day to propagate is an annoyance; a key removal that takes a day to propagate is a serious security concern.
Keeping in mind the importance of removal being easy, that suggests a few approaches:
It sounds like you already have some way of creating the users quickly. There is a good chance that's LDAP, for example. LDAP can store SSH public keys, and you can hook this in to sshd using the configuration option AuthorizedKeysCommand. For example, if you're running SSSD, sss_ssh_authorizedkeys is intended for that. (See, e.g., RedHat docs on SSSD authorized keys). Key addition and removal can be instant, worst case is typically a few seconds for LDAP propagation. You can very likely fully automate this (and if you have a bunch of users probably already have!), requiring no admin intervention.
If your servers must handle authentication offline (and beyond what SSSD can do), another approach is to use the certificate authority (CA) support in OpenSSH. This is documented mostly in the ssh-keygen manpage’s “Certificates” section. Basically you set up your servers' sshd to trust your CA and to automatically fetch update revocation lists. Then you sign the client's public key with said CA and give the cert to the client. At that point, the client can log in to all the servers using said cert. To un-authorize the client, you add it to the revocation list (as explained in the immediately following section in the man page). Key addition is instant, removal depends on how often you update revocation lists. Unfortunately there isn't anything like OCSP for SSH CAs. Automation (without admin help) of adds is possible to do securely; of removes is easy.
You could—as you suggest—use shared, auto-mounted (or permanently-mounted; auto-mount is not required) home directories so all servers see the same ~/.ssh/authorized_keys — but this is a lot of overhead if you otherwise don't need a shared $HOME. Key addition and removal are instant to fairly quick, depending on caching. Key management likely entirely done by the user, not an admin.
3b. Ulrich Schwarz points out that you can change the location of the user's authorized keys file; it doesn't need to be ~/.ssh/authorized_keys. So you could share a directory containing all users' authorized keys files, and not have the overhead of fully shared home directories.
You could use your configuration management tool like @DopeGhoti suggests. Be very careful not to forget about a host—especially one where the key was manually added. Probably means key addition and removal will require manual intervention by the admin.
Best Answer
Assuming your username is
testssh:/etc/ssh/authorized_keys_testsshand put your key there/etc/ssh/sshd_config:and restart sshd. Your user will be able to ssh with his private key.