RME 3.5 is obsolete, and no longer supported. Additionally, RME 3.5 only supported SSHv1, so any devices that answer with v2 only would fail. Additionally, if you did not have Common Services 2.2 SP 3 applied, any device which replied with SSH-1.99 would also fail. No, there was no key cache.
You should strongly consider upgrading to LMS 3.1 which includes RME 4.2. This latest version supports both SSHv1 and SSHv2.