Ubuntu – Ubuntu 12.04 – I can ssh into the server but sshd is an unrecognized service

I'm trying to setup key based authentication for ssh on my Ubuntu 12.04 server following this tutorial and that.

It's not really working but I have another problem slowing me down, which is that I can't restart the ssh service.

I can ssh to the server without any trouble. If I do ps aux | grep -i "ssh" I can see the sshd process but if I do service sshd restart then I get "sshd unrecognized service". I can restart ssh but I take it that's a client, not a server.

If I Google "sshd unrecognized service" I get to know all about troubleshooting ssh connectivity but that's not my problem.

I tried purging and reinstalling openssh-server, to no effect.

How can I restart the sshd service if that service doesn't exist?