Isn't that problem solved by using centralized authentication server instead of distributing the authentication material on individual servers? I imagine that would be best practice regardless of authentication method.
Personally I find a yubikey to be the best middle ground. Your private key is stored in the secure element and can never be removed from the hardware. You protect that also with a password, and the key must be physically touched to be activated.
Given the extremely bad consequences of the authentication server's failure and the load it might be under for a fleet of 1000s of servers, that would probably require a fairly sophisticated clustering/HA approach. That is a lot of effort to spend compared to writing ensure => present and ensure => absent for a bunch of SSH keys in Puppet, which anecdotally seems to be what a lot of major companies do.