Same here, at least privately - it happened a couple of times that I renewed or changed for whatever reason the key on some server and a few days later when I tried to connect using a secondary device I got the warning, which made me go to defcon-2 for at least a few minutes, hehe.
On the other hand, at the company I work for, internal machine certificates/keys are renewed without my involvement (I'm a so-called "IT-owner" of some apps and the infrastructure that the apps use), and therefore I get the warning when connecting to their Linux hosts but each time (few times every few years, but still...) I dismiss it hoping that it's because of the work of the admins renewing the certificates (clarifying who-did-what-when would be a potential major administrative undertaking) => this is absolutely a flaw of the internal processes.
Yes, it could be fixed by a more complex infrastructure, but again, if the internal processes are weak then even the more-complex-infrastructure could be compromised by side-attacks.
