The purpose of this file is well explaines on the following link: http://en.wikibooks.org/wiki/OpenSSH/Client_Configuration_Files#.7E.2F.ssh.2Fknown_hosts
Let's say that we have a network with 100 servers and each time we add another server to this network all the machines need to update the known_hosts file with the new public key.
First step: ask the new machine for it's public key with ssh-keyscan:
# ssh-keyscan localhost/remotehost
# localhost SSH-2.0-OpenSSH_5.3
localhost ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAQEAygRKDjzHw1a1L79f5rNaGlqPUDndZv9KhtZPG2MYrUrU/9NiBOiVDWwllUwWXQkLY3fhdTVncjGfzn4oc09876J3uXZJaNWr0PZpD8S7Y6+50iZWYVA0fTM0j32WdD3MMfJjCtrXo+/gDx9+XiQPXlWqkuy5L5PRIvjIzVeZwL6BDDalmQXx3Jw5QcfQn9Bc7m+Bw7ZO80mxnFnKH5zZa8jdjd6XPSLXN0Q+5UlvZ5o5hxaFA+4ywtvKbF6avlQj5rm9+6kGUkVLIZRVw+lkkGqSixsTMGC3mZURH2s38UB1OjHXQSW8DP/mImcAAQWB3V5JDHbswee99C8CU6ekcw==
And manually append the output to your ssh_known_hosts/known_hosts file in the proper format (man ssh-keyscan):
Output format for rsa1 keys:
host-or-namelist bits exponent modulus
Output format for rsa and dsa keys:
host-or-namelist keytype base64-encoded-key
Where keytype is either “ssh-rsa” or “ssh-dss”.
Distribute this file with a puppet class on your nodes and you won't be prompted again to add this new key into your known_hosts/ssh_known_hosts file at the first login attempt.
For sure this is far from perfect, but solves the problem in a short time.