Per @revinder in a comment:
I solved it my own server sending the two packets merged into one, the SSH2_MSG_KEX_DH_GEX_REPLY and the SSH2_MSG_NEWKEYS.