The ECDSA key hasn't changed. As pointed out elsewhere in this thread, the official command `ssh-keygen -R github.com` is incomplete -- it doesn't remove IP address entries, they need to be removed manually. What you got was a conflict between the ECDSA key and the old RSA key left over in ~/.ssh/known_hosts (the error message was unclear).

Since GitHub's IP address is not stable, I suggest disabling the IP-checking feature using

    Host github.com
         CheckHostIP no

The CheckHostIP feature is pretty useless anyway, it just gives a warning when the IP changes and gives a better diagnostic message if the key and IP both change at the same time (references: https://serverfault.com/questions/1040512/ssh-how-does-the-o..., https://unix.stackexchange.com/questions/285520/why-does-ssh...).