2008年のOpenSSHという時点でほぼ無理でしょう。今当然に使える楕円曲線暗号なんかも、当時は使えなかったはずですから。
※リリースノートによれば、2011年のバージョン5.7で初めてECの対応が出てきてます。
※それよりもハッシュのsha2/sha256の対応の方が致命的かもしれません
さて、"no kex alg"というのは、KEX(鍵交換)としてサーバ(github側)が許容できるアルゴリズムをどれも、クライアント(CentOS5側)で使うことができなかったということです。
なので、サーバ側の設定を緩くして対応することは(論理上)可能でも、クライアント側で何か設定してどうなるものではありません。
一応確認方法としてですが、以下のように敢えて強度の低い鍵交換アルゴリズムを指定してsshコマンドを実行することで、サーバの許容できる鍵交換アルゴリズム一覧が"Their offer:" 以下で分かりました。いずれもcurve25519やecdhといった楕円曲線暗号です。( 素のDHも混じってますが、それもsha256と組み合わせた新しい方式です )
$ ssh -o KexAlgorithms=diffie-hellman-group1-sha1 git@github.com
Unable to negotiate with 192.30.255.112 port 22: no matching key exchange method found.
Their offer: curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256
私の環境でクライアントとして使える鍵交換アルゴリズムは次の通りなので、githubもちゃんと使えますが。同じようにして対応しているアルゴリズムを調べてみれば、より確かかと思います。
$ ssh -V
OpenSSH_7.2p2 Ubuntu-4ubuntu2.1, OpenSSL 1.0.2g 1 Mar 2016
$ ssh -Q kex
diffie-hellman-group1-sha1
diffie-hellman-group14-sha1
diffie-hellman-group-exchange-sha1
diffie-hellman-group-exchange-sha256
ecdh-sha2-nistp256
ecdh-sha2-nistp384
ecdh-sha2-nistp521
curve25519-sha256@libssh.org
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。