Using an SSH Certificate Authority is also my recommendation, but be aware that it's relatively new, so associated tooling with it is not super mature yet. In particular, the user still needs some bits in order to login, and whether they generate it themselves and send it off to get signed, or the bits are generated for them on the backend and the user simply needs to receive them, there's a management aspect to it that isn't a totally solved problem with open source tools.

It's not a difficult problem, mind you, but there was custom code written that runs on developer laptops (OS X and Ubuntu) to support this workflow.

(Despite being a very similar looking string of bytes as more traditional pub/private keys, it's different in the SSH-Agent protocol, so don't assume all ssh-agent-looking daemons support it.)