After following all the instructions on GitHub around setting up ssh access, I was still failing to check out a repo. Was seeing the following error:

Host key verification failed. fatal: Could not read from remote repository.

Turns out you need to manually add an entry into known_hosts:

ssh-keyscan -H github.com >> ~/.ssh/known_hosts

H/T to Tupy at StackOverflow