I understand the concepts behind key based SSH authentication, I'm just looking for suggested "best practice".

Situation: Small company* using SSH to access various** Linux servers, some internal, some external, currently using password-based SSH for most of this, sometimes key based but managed on an ad-hoc basis.

Many of the clients are Windows based using PuTTY.

I want to shift everything to key based, and that requires me managing the keys. In particular I want to be able to add a new user (and therefore a new key), add it to servers as required (so not all users will have access to all servers), and remove keys if required too (eg someone leaves).

As a starting point, I can create public/private key pairs for each user, add them manually to authorized_keys on appropriate hosts, and give each user their private keys (in PuTTY's PPK format as needed). That leaves me with several keys to manage securely, and a bit of a maintenance headache keeping track of who is authorised where.

Suggestions?

* Small means, in this case, 3 users, but with plans to expand. ** Various means probably a dozen (maybe twice that) VMs, hosted servers, etc, using a mixture of Debian and Ubuntu.