Este é um sistema CentOS. Você não estava reinstalando o pacote inteiro. Os pacotes relevantes para o OpenSSH são: openssh , openssh-server e openssh-clients . O binário sshd faz parte do pacote openssh-servers .
Experimente yum reinstall openssh openssh-server openssh-clients e veja se isso funciona.
Em geral, para verificar a consistência dos pacotes no sistema, você pode usar o rpm verify.
rpm -vV packagename para um pacote individual.
ou
rpm -vVa para verificar a consistência de todos os pacotes instalados.