An alternative (but also imperfect) solution that I've relied on in the past is using certificate-based authentication:
https://www.digitalocean.com/community/tutorials/how-to-crea...
This still requires the generation of certificates for users but it doesn't require updating the key material on the servers themselves. Having short-lived user certificates then gives the admin an easy way to revoke access to a server without changing any keys there by simply not issuing a new certificate to the user (and in urgent cases to also revoke the certificate as well before it expires, which requires intervention on the server though).
I really hope that OpenSSH keeps improving their (still largely incomplete) PKI implementation, as I think it's a great feature for larger organizations.