On two specific nodes, I get "Permission denied" when the script tries to log in.

On two? Does it do this on other's as well or only those two? Might help resolving what's going on here

Dose this mean that Net::SSH::Perl is not using password authentication, and is trying to use an rsa key?

I did see something on the perldoc page suggesting it can read identity files. I haven't done it this way myself however. Have you tried removing the RhostAuthentication option in your code? Everything else looks similar to what I've seen done. Just a thought.