Por que no agregas el nuevo fingerprint a esos dispositivos de manera automática? En cada dispositivo ejecutas lo siguiente:
ssh-keyscan <host> >> ~/.ssh/known_hosts
O en caso de que tu host sea algo viejo
ssh-keyscan -t rsa,dsa <host> >> ~/.ssh/known_hosts
Si quieres evitar entradas duplicadas (en caso de haber aceptado el fingerprint nuevo en algunos dispositivos y no en otros)
ssh-keygen -R <host>
ssh-keygen -R <ip_address>
ssh-keygen -R <host>,<ip_address>
Con eso te aseguras de que no quede ninguna entrada del host antes de usar el ssh-keyscan.
Puedes automatizarlo todo con herramientas como Fabric, Ansible, pssh, etc. Hay un montón de ellos que te evitan hacerlo a mano.