Here's the simple scenario. Of course, you can extend and change it if necessary.

1. On the first connection to a certain host, the application shows the server key to the user and asks the user whether he trusts this key AND whether this key should be saved as trusted for future use. If the user trusts the key, continue the connection. If the user has chosen to save the key for the future, save it. Also, the application can save the key of the server for reference purposes (see below).


2. On subsequent connections, first check whether the key is present in the list of trusted keys for the server you are connecting to. If it's present, continue connecting. If the key is not present AND there's no reference key saved on the server, ask the user (as described above). If the reference key is different from the one you are validating, warn the user that the key is different and again let the user decide, as described above.