Though for new hosts people often don't verify the initial host key at all, just blindly accepting it, so that would be an extra risk vector.

Heck, I'm sure many don't bother verifying a new key when they get the warning, instead just removing the old from .ssh/known_hosts (or equivalent) to quiet the complaining! Though to be honest, with that security posture nothing is going to save them and our efforts are better spent securing others! I know at least one of our clients has automated systems that ignore key changes, because we once had a temporary config cockup that sent some connections to a host with the wrong key and some data was received there without any reported issues…