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.