Stop authenticating users via keys directly to a server. Use Kerberos v5. This centralizes the authentication to one or a set of servers. You then don't need to clean up key mess everywhere. Once you're running Kerberos you can choose the method of authentication to the central server. You can use password, public key (but only one in this case), OPIE (One-time Passwords In Everything), Google authenticator, RSA securid, biometrics, SRP (Secure Remote Password), or any combination of these to make things 2, 3, 4 or X factor authentication. The sky is the limit, and there's no crazy mess to have to follow up with.
When you need to have things automated, and you must use key authentication, then make sure that the area the key authenticates to is well sandboxed with something like a FreeBSD jail with access to nothing but the resources needed for the remote function to be performed.
This is all using standard practices that are over a decade old (and clearly spelled out in the FreeBSD Handbook among many other places).