Это какая-то особенность кастомизации /etc/pam.d/system-auth-use_first_pass в тех дистрибутивах, где наблюдается это явление.  К openssh все это не имеет никакого отношения.

Просьба проверить в свежих дистрибутивах на p6 и либо закрыть, либо перевесить на того, кто все портит.

(В ответ на комментарий №1)
> Просьба проверить в свежих дистрибутивах на p6 и либо закрыть, либо перевесить
> на того, кто все портит.
Проверял несколько раз на последних p6 - проблема присутствует.
Если бы я знал кто это порти, я бы перевесил, а так я проблему вижу непосредственно в ssh, поскольку вызываю непосредственно его.

(В ответ на комментарий №1)
> Это какая-то особенность кастомизации /etc/pam.d/system-auth-use_first_pass в
> тех дистрибутивах, где наблюдается это явление.
В 5.1 файл /etc/pam.d/system-auth-use_first_pass фактически идентичен, но этой проблемы нет.
Отличие всего лишь в префиксе prefix=$2a$ и prefix=$2y$, а их выравнивание проблемы не устраняет.

Кстати, речь о сервере не идёт и он всегда тот-же.

То же самое наблюдается на системе с текущим p6 (i586), полученной так:
Desktop 4.1 -> branch 4.1 -> branch p6
(пока был 4.1 - было всё хорошо).
И не наблюдается на установке 6.0.0_beta20110815-kdesktop-x86_64,
обновлённой до текущего p6.

Сервер один и тот же - текущий branch 5.1.
Вход разрешён только по ключу.

На обоих клиентах pam-config-1.5.3-alt1.

На "неругающейся" системе (x86_64):
# rpm -V pam-config
S.5....T c /etc/pam.d/system-auth-krb5
(на ругающейся - всё в порядке).

Разница для "неругающейся" системы такая:
# diff -Nau tmp/system-auth-krb5.orig /etc/pam.d/system-auth-krb5
--- tmp/system-auth-krb5.orig   2011-08-12 22:59:45.000000000 +0400
+++ /etc/pam.d/system-auth-krb5 2011-08-27 21:39:04.396456215 +0400
@@ -1,8 +1,9 @@
 #%PAM-1.0
 auth           [success=2 default=ignore]      pam_tcb.so shadow fork prefix=$2y$ count=8 nullok
 auth           requisite       pam_succeed_if.so uid >= 500 quiet
-auth           required        pam_krb5.so use_first_pass
+auth           required        pam_krb5.so use_first_pass ccache=/tmp/krb5cc_%u
 auth           required        pam_permit.so
+auth     optional       pam_mount.so
 
 account                [success=2 default=ignore]      pam_tcb.so shadow fork
 account                requisite       pam_succeed_if.so uid >= 500 quiet
@@ -20,3 +21,4 @@
 session                required        pam_mktemp.so
 session                required        pam_mkhomedir.so silent
 session                required        pam_limits.so
+session  optional       pam_mount.so

На "ругающейся" системе при первом входе (который не выполняется) выдаётся:
Agent admitted failure to sign using the key.
ssh: Permission denied (publickey).

В логах ругающейся системы заметил такое (/var/log/auth/all):
Jan  2 20:01:51 sasha ssh-agent[23168]: fatal: ssh_askpass: exec(/usr/lib/openssh/ssh-askpass): No such file or directory

В логах сервера (/var/log/auth/all):
Jan  2 20:01:51 testserv sshd[19076]: Connection closed by 89.178.66.245
Jan  2 20:04:09 testserv sshd[19115]: Accepted publickey for sasha from 89.178.66.245 port 27597 ssh2
Jan  2 20:04:09 testserv sshd[19115]: pam_tcb(sshd:session): Session opened for sasha by (uid=0)
(последние 2 строчки - второе, успешное, соединение)

Файлов /usr/lib*/openssh/ssh-askpass нет ни на одной системе.

Куда ещё посмотреть?

Ветка p6 давно EOL, неактуально.