git - issue with ssh keys

I've been getting this a lot and I've read through the error messages to try and resolve this. I'll delete my key on git and re-add this. However, I do notice I can correct this by simply rebooting my mac. But I don't want to do this every time I get the errors below. So what is the real problem? Why does a reboot of my machine fix this? Is there something misconfigured? I'm ruing OSX El Capitan (10.11.1)

See this:

$ git pull origin master
The authenticity of host 'github.com (192.30.252.128)' can't be established.
RSA key fingerprint is SHA256:nThbg6kAUpJVGl7E1IGOCspRomTxdJACKviKwASSSY8.

    Are you sure you want to continue coecting (yes/no)? yes
    Waing: Permanently added 'github.com' (RSA) to the list of known hosts.
    ERROR: Sorry, but @YourCompany has blocked access to SSH keys created by some third-party applications. Your key was created before GitHub tracked keys created by applications, so we need your help.

    If you personally created this key, you can approve it at:

      https://github.com/settings/ssh/audit/4586954/policy

    Otherwise, please upload a new key:

      http://git.io/KM0rtw

    Fingerprint: 03:aa:d6:43:a4:8d:37:fd:65:24:6c:95:78:67:51:65

    [EPOLICYKEYAGE]

    fatal: Could not read from remote repository.

    Please make sure you have the correct access rights
    and the repository exists.