According to Github security blog RSA keys with SHA-1 are no longer accepted.
Use the following command to create new SSH key with ECDSAencryption and add it to Github.
ssh-keygen -t ecdsa -b 521 -C "[email protected]"
Original answer with details can be found here