Have you considered creating Certificates for your keys? The basic idea is that you have a master CA key pair which you use to sign all your actual keys with (ideally both use and host keys). Than you only add a CA entry for the CA to the authorized_keys and known_hosts on every machine and now, whenever you add a user or host, you only need to sign its keys and everything else trusts it automatically. Add a CRL for key revocation to solve the lost-keys-problem and not you should have everything you wanted. All of this comes out of the box with OpenSSH, no extra tools required.