How would one stage a MITM attack without knowing the private key corresponding to the old key?
If your system doesn't know the public key of an SSH server, when you connect the first time, the SSH client will display a warning and ask you if you accept the server key. An attacker could be between you and Github and if you accept without checking it's the correct key, you would be toast.
edit: I found this helpful and honestly had no idea I should be doing this (I’m a hobbiest not a professional) https://bitlaunch.io/blog/how-to-check-your-ssh-key-fingerpr...
Meaning that a lot of users will blindly accept whatever new key (even when it might be the one owened by attacker doing MITM) because Github, their college or random person on internet said that that's what you have to do to get rid of error.
This is less likely because unlike for TOFU the SSH client just rejects the mismatch and insists you take manual action, and the likely manual action will be "Paste this stuff from the announcement".
So an adversary needs to either subvert whatever messaging you see (which is tricky, likely impossible for a random user visiting the github web site wondering what's wrong) or hope that you just try to muddle along and do TOFU again, putting you in the same spot as a whole bunch of users every day at GitHub.
The problem here is that their first command that they advise using is the one that removes the old key and most users are just going to stop right there because it solves the problem of getting the key warning.
The right solution here is to provide a command that most users are going to copy and paste that deletes the old key and adds the new key all at once.