It seems the GitHub message is genuine, though looking through Twitter suggests there is a lot of unhappiness about the way the message was spread, its timing and its content.
Not sending such a message from your own mailservers also looks very foolish to me – checking the headers of a dodgy looking email is, I am sure, the first thing many of us do when we are not sure.
Anyway, as GitHub don’t tell you – here is how to do what they are asking (approve as valid your SSH keys):
ssh-keygen -lf ~/.ssh/id_rsa.pub
And check the output against GitHub’s public key.
cartesian product 