"No ECDSA host key" error connecting to GitHub

Network guy provided the answer. I had to run the following command on the Jenkins server, as the Jenkins user, to get a proper known_hosts file.

ssh -T git@github.com

After this, restarted Jenkins and it worked fine.