[emn13]

Sure, but the difference is that it's now both a plausible moment to go MITM (because they got that key), and furthermore the hypothetical attacker now has good reason to believe users won't be scared by a host-key-change warning, and the hypothetical attacker would know this opportunity exists for a large set of users simultaneously. If some malicious network operator were to try and exploit users, now would be a good moment - they'd likely catch many more people in the time it takes to be discovered than on an average day.

The MITM-at-the-start risk is of course real, but I think this new everyone -restarts-simultaneously risk is qualitatively different enough to be worth at least considering.

[lxgr]

Much more concerningly, there is an activated-by-default OpenSSH extension (`UpdateHostKeys`) that allows the server to install new host keys into `.ssh/known_hosts` after every successful server authentication.