I was just going to submit this thread, thinking how in the ** could the github host key being changed. Leading to their blog post explaining it. Their exposed their private RSK key!

    ssh-keygen -f ~/.ssh/known_hosts -R github.com

Now it's a ED25519 with +DiY3wvvV6TuJJhbpZisF/zLDA0zPMSvHdkr4UvCOqU (they don't list this on their blogpost, just their renewed RSA key)