SSH keys work exactly like self-signed certificates. On first connection you get the "whoah, this isn't trusted, do you want to proceed" warning, and if you accept, you are not warned in the future unless the key changes.

If browsers would make it easier to "permanently accept" a self-signed certificate (right now it's usually a multi-step process with blood-red warning messages at every step) we'd have the same situation as SSH keys.