Read @cupcake's answer for explanations. Here I only try to automate the fix.
If you using Cygwin terminal with BASH, add the following to $HOME/.bashrc file. This only starts ssh-agent once in the first Bash terminal and adds the keys to ssh-agent. (Not sure if this is required on Linux)
###########################
# start ssh-agent for
# ssh authentication with github.com
###########################
SSH_AUTH_SOCK_FILE=/tmp/SSH_AUTH_SOCK.sh
if [ ! -e $SSH_AUTH_SOCK_FILE ]; then
# need to find SSH_AUTH_SOCK again.
# restarting is an easy option
pkill ssh-agent
fi
# check if already running
SSH_AGENT_PID=`pgrep ssh-agent`
if [ "x$SSH_AGENT_PID" == "x" ]; then
# echo "not running. starting"
eval $(ssh-agent -s) > /dev/null
rm -f $SSH_AUTH_SOCK_FILE
echo "export SSH_AUTH_SOCK=$SSH_AUTH_SOCK" > $SSH_AUTH_SOCK_FILE
ssh-add $HOME/.ssh/github.com_id_rsa 2>&1 > /dev/null
#else
# echo "already running"
fi
source $SSH_AUTH_SOCK_FILE
DONT FORGET to add your correct keys in "ssh-add" command.