The code that is currently running is the IP only image and it does not support SSH. To support SSH you need an image with crypto support and so yes you will need to upgrade the code.
I checked in the software advisor on the Cisco site to find equivalent code that would support SSH. I find c3660-ik9s-mz.12.2-16d which is the IP PLUS IPSEC 3DES image to probably be the closest match to your current code. Of course if you upgrade code you might consider upgrading to a more recent version of code. Be aware that the requirements for flash and for memory are different in these 2 versions. While the IP only code requires 8 MB of flash and 32 MB of memory the IP PLUS IPSEC 3DES code requires 16 MB of flash and 64 MB of memory. Check the router to verify whether it has those resources.
In addition to the good suggestions made by Sunday and Amit it would be helpful to see the output of show ip ssh.
The fact that an access list is written to allow SSH does not necessarily indicate that SSH is running on the router. And there being no transport input ssh does not mean that SSH is necessarily disabled since the default is transport input all which does include SSH. The invalid command response to the attempt to generate RSA keys is a strong indicator that the image being run does not include crypto support. The output of show ip ssh would confirm the status of SSH.
We are pleased to announce availability of Beta software for 16.6.3. 16.6.3 will be the second rebuild on the 16.6 release train targeted towards Catalyst 9500/9400/9300/3850/3650 switching platforms. We are looking for early feedback from custome...