After starting the ssh-agent using:
eval $(ssh-agent)
Then you need to add a key for that use:
ssh-add
This will ask you your passphrase just once then you should be able to push it to github.
To add the key permanently use:
ssh-add -k
This will store the key and will not ask for passphrase again.