In the enterprise world, engineers often ssh into hosts for the first time on a daily basis. This trains them to acknowledge the trust on first use prompt on a daily basis.
Sharkey removes the prompt by signing the openssh certificates.
Feel free to post questions here and I'll relay them.
Did you look at RFC4255?
It also becomes more complicated when you are running multiple ssh services on a single host or using proxies/forwarders.
I use a similar method to secure my own ssh services before that I used a tool that converts the fingerprint into a phrase but it wasn't collision resistant enough.
We could use RFC4255 instead, but we'd still have the same problems around issuing them, and we could set up sharkey to support it if we wanted to.