When using SSH Diffie Hellman key size 4096 then we can no longer manage our cisco devices. As per support this is not yet supported and should be raised as a new feature.
Case # 1067613
(Optional) Specifies the IP size of the key modulus.
By default, the modulus of a certification authority (CA) key is 1024 bits. The recommended modulus for a CA key is 2048 bits. The range of a CA key modulus is from 350 to 4096 bits.
Note | Effective with Cisco IOS XE Release 2.4 and Cisco IOS Release 15.1(1)T, the maximum key size was expanded to 4096 bits for private key operations. The maximum for private key operations prior to these releases was 2048 bits. |