Jenkins - Resolve No ECDSA Host Key Issue

On my freshly deployed Jenkins instance, I got the following error message after trying to hook up my first GitHub repository:

stderr: No ECDSA host key is known for github.com and you have requested strict checking.
Host key verification failed.
fatal: Could not read from remote repository.

Luckily this is easy enough to fix.

Steps

Go to the Manage Jenkins page, and click on Configure Global Security.

Scroll down to the bottom where it says Git Host Key Verification Configuration, and change it to Accept first connection before clicking the Save button.

Now go back to your repository and try again (re-indexing branches for me).