Oui openSSL est bien installé. Dans /lib voilà ce que j'ai :

# ll /lib/libcrypto.so.*
-rwxr-xr-x 1 root root 1155236 Oct  2  2006 /lib/libcrypto.so.0.9.7a
lrwxrwxrwx 1 root root      19 Feb 17 04:19 /lib/libcrypto.so.0.9.8 -> libcrypto.so.0.9.8b
-rwxr-xr-x 1 root root 1241936 Oct 10  2007 /lib/libcrypto.so.0.9.8b
lrwxrwxrwx 1 root root      19 Feb 16 19:03 /lib/libcrypto.so.4 -> libcrypto.so.0.9.7a
lrwxrwxrwx 1 root root      19 Feb 12 08:05 /lib/libcrypto.so.6 -> libcrypto.so.0.9.8b
lrwxrwxrwx 1 root root      24 Feb 16 19:27 /lib/libcrypto.so.7 -> /lib/libcrypto.so.0.9.7a

J'ai essayé le lien symbolic, mais rien n'y fais.

J'ai regardé dans ton les packages openSSL fournis avec Red Hat 5 et il n'y a cette lib.

Voila les packages installés:
openssl097a-0.9.7a-9
openssl-0.9.8b-8.3.el5_0.2

openssh-4.3p2-24.el5
openssh-clients-4.3p2-24.el5

Dans la doc j'ai bien respecté les prérequis :
Requiere:
--------
OpenSSH 3.8.1 (ou superieur)

Optionnel:
----------
OpenSSL 0.9.7 (ou superieur) pour l'extension : verification des donnees

Non, mais j'ai récupéré la lib d'une Debian. Je sais pas si c'est top mais le serveur ce comporte bien, de plus il ne sert qu'à çà.