The problem is definitely not your key; it's most likely the server's Diffie-Hellman parameters -- or possibly their DSA key, but not too many people use DSA keys for SSH, especially since OpenSSH deprecated them recently. It might be worth taking a network trace to see exactly when the error is occurring: on initial negotiation of e.g. group14; or DHGEXgroup and its params; or DH(GEX)reply containing a DSA signature and that signature.
If you're using Sun/Oracle Java before version 8, it can't handle DH (or DSA) sizes above 1024, but DH size 1024 is now considered vulnerable so many servers use 2048. See https://weakdh.org and http://www.keylength.org and/or the many Qs mostly on security.SX and crypto.SX about Logjam. In this case you have two choices: upgrade to Java 8, where DH (and DSA) 2048 works; or if the server supports ECDH and the SSH library you are using and can't change also does but you're using Java 6 (or lower?) which doesn't, add the provider from http://www.bouncycastle.org which does support ECDH, which generally is preferred over classic-DH and thus avoids the problem.
If you're using IBM Java, as I wildly speculate from the possibility MF -> mainframe -> IBM mainframe -> IBM shop, this answer doesn't apply directly. IBM Java uses IBM cryptoproviders which are different from the Sun/Oracle cryptoproviders in Sun/Oracle Java. However, if you check their documentation for DH parameter sizes and possibly DSA parameter sizes, there might be something similar.
If it isn't DH, then definitely look at a network trace, and if you can't figure it out, add the relevant parts to your question.