Ok so I've picked this up again after having to attend to more urgent matters. For testing purposes I set up two VM's on my laptop. One is running RHEL 6 and the other is running Solaris 10. Both for x86 platform.
I can successfully set up key pairs between the two VM's using the methods mentioned in this thread. (Log in without password from Redhat machine to the Solaris machine).
I then tried to set up a key pair between my Redhat VM and the Solaris server I'm actually trying to get it working on and it doesn't work. So that's two different versions of Redhat that doesn't work but it works from the Redhat VM to the Solaris (latest version 10 x86) VM.
I noticed that the ssh package versions are slightly different between the two Solaris instances. I can't however get that version because the server is running on the SPARC platform and already has the latest ssh package for version 10.
If there are any more ideas out there feel free to comment. Just putting it out there