sudo をコマンドの前につけて実行していますか。

蛇足ですが、ubuntu でデーモンの再起動等の操作をするときは sudo serivce ssh restart のように「service」コマンドを使うのが推奨されていて、「/etc/init.d」のスクリプトの使用は非推奨です。

設定が反映されないとのことですが、何を反映させようとどのような修正を施し、sudo /etc/init.d/ssh restart (推奨は sudo service ssh restart) の実行後、どのようにして確認したのかを提示していただかないと、先の回答以上の情報は得られないと思います。

jeno による投稿:

PasswordAuthenticationをyesからnoに変更しました．

まさかと思いますが、/etc/ssh/sshd_config ファイルの PasswordAuthentication の行は行頭に # がついていますが、これを残したままということは無いですよね。
# にはこの文字から行末までをコメントにするという意味があるので、#PasswordAuthentication yes を #PasswordAuthentication no に変更しても動作に影響ありません。
行頭の # も削除して PasswordAuthentication no にしてください。

試しに sudo /etc/init.d/ssh restart としたら、何かをしたような様子は見られませんでした。
/etc/init.d 以下を直接実行したときと service コマンドで実行したときとで、環境変数が異なるということなのでそれが影響している可能性があります。
sudo service ssh restart は試されましたか。