SSH certificates avoid this issue and are used in real life. We make them with hashicorp vault, it works well and is really convenient.
I'm generally just spinning up a fresh Ubuntu instance on EC2, so I have an entirely 'vanilla' SSH set-up. Small scale, so I don't especially mind the ritual of verifying the fingerprint. It's annoying though that it takes a few minutes for the EC2 system-log to be populated with the 'true value' of the fingerprint.
Presuming you mean X.509 certificates, is this part of the standard spec (e.g. should work with OpenSSH etc)? Do you know if it works with PuTTY?