Interessante, eu gostaria que essa configuração funcionasse, mas eu poderia reproduzi-la também.
No entanto, o contrário funcionou bem para mim:
PasswordAuthentication no
# other configuration (...)
Match User root
PasswordAuthentication yes
Parece que o não-operador não se comporta como esperávamos. Estranho.