I key-gen'd new ed25519 keys, loaded to GitHub, deleted the retired ssh private keys, restarted the SSH server, re-added the new key, tested it:
ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIOTRWZ1iXwJS9jPsv/dcgxCg2rjNnOi+iO59loLav617 email@gmail.com
Everything AOK on my side.
Then, I rebooted my server, re-gen'd new keys and started the entire process over from scratch.
Same same.
No changes made to .gitconfig (global) nor $GIT_DIR/.gitconfig (Local)
Ah, but then, in unrelated (?) news, GitHub 'informed' me that I needed to update my GitHub (online) account which I promptly did. Ya think? I logged into my GitHub account, added rekey-1 and rekey-2(nd attempt) successfully -
1: The push
git push origin master
git@github.com: Permission denied (publickey). fatal: Could not read from remote repository.
Please make sure you have the correct access rights and the repository exists.
Step 2: Ran the ssh telnet test
ssh -T git@github.com
git@github.com: Permission denied (publickey).
Step 3: Ran the Debug test
ssh -vT git@github.com
Issue occurred after I cleaned (removed) 'excess keys' from GitHub Authentication keys not realizing that a public key is needed in both authent and signing.