By far the most effective measure is to go keys only for your ssh logins.
Then have your users generate keys,
$ ssh-keygen -C "firstname.lastname@example.org"
(There are other options to play with, see ssh-keygen(1) for inspiration.)
Then add the *.pub to their ~/.ssh/authorized_keys files.
A dirty little secret: you can even match on interface in your sshd config for things like these