The client and the server begin by sending to each other the protocol and software versions they are using.
SSHv2 Client: Key Exchange Init
Here, the client tells the server the algorithms it supports for each function (encryption, MAC, key exchange, host authentication, compression), in order of preference.
SSHv2 Server: Key Exchange Init
The server does the same. Note that it can send this message before it has received the one from the client.
From the two lists of algorithms, the client and the server compute independently the same cipher suite. For instance, they choose the same kex exchange algorithm (and it takes place right after that).
SSHv2 Client: Diffie-Hellman Key Exchange Init
SSHv2 Server: Diffie-Hellman Key Exchange Reply
SSHv2 Client: Diffie-Hellman GEX Init
SSHv2 Server: Diffie-Hellman GEX Reply
The Diffie-Hellman key exchange enables the client and the server to end up with a shared secret that an observer on the network cannot feasibly guess. For example, they will derive a key for the encryption algorithm from this secret.
Note that the reply of the server also contains its public host key (or certificates). If it is a public key and the client has never seen it, the client usually asks the user if it should trust it:
The authenticity of host 'debian.org (126.96.36.199)' can't be established.
ED25519 key fingerprint is SHA256:bNnjFMvzsNhkwzRHwGRbTIUM4XzUjlLrBl/7MzCbndw.
SSHv2 Client: New Keys
With the New Keys message, the client means:
Hey server! All the following messages from me will use the ciphers we just negotiated.
The server must also send a New Keys message to the client.
My main reference is the RFC for the SSH Transport Protocol: https://tools.ietf.org/html/rfc4253. This is the lowest layer of SSH, on which all other SSH services (user authentication, shell, X11 forwarding, etc) are based.