[arianvanp]

It doesn't matter because it didn't change! That's the beauty of TOFU.

One way to solve this in TOFU is to have a time window where both keys are presented.

[justeleblanc]

If we're starting from the assumption that the first key was compromised, then you're still vulnerable to MITM. The only solution is communicating the key through a different, trusted way. Which is exactly what github did - inasmuch you can trust that github.com is github.