jenkins complains host key verification failure although the key was generated

Error:

Fetching upstream changes from git@github.com:....../.........git
ERROR: Problem fetching from origin / origin - could be unavailable. Continuing anyway
hudson.plugins.git.GitException: Error performing command: git fetch -t git@github.com:....../......git +refs/heads/:refs/remotes/origin/
Command "git fetch -t git@github.com:...../......git +refs/heads/:refs/remotes/origin/" returned status code 128: Host key verification failed.
fatal: The remote end hung up unexpectedly

My comments:

1> I found that jenkins build fails when it executes ; git fetch -t git@github.com:...../......git +refs/heads/:refs/remotes/origin/

2> Executed the folleing to ensure the key works: -
ssh -T git@github.com
Hi [username]! You've successfully authenticated, but GitHub does not provide shell access.

But when I pasted the same command on the command line it executes it successfully: weird!

Any help ASAP is much appreciated .

---