SSH session will not create a shell

Environment:
Red Hat Enterprise Linux Server release 6.10 (Santiago)

Issue:
After a recent upgrade to the OS we cannot SSH to the server. When we try the session connects and the user authenticates but the shell does not build at all. The session just hangs.

Output of ssh -vT
OpenSSH_5.3p1, OpenSSL 1.0.1e-fips 11 Feb 2013
debug1: Reading configuration data /root/.ssh/config
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Applying options for *
debug1: Connecting to somehost [xx.xxx.xx.xxx] port 22.
debug1: Connection established.
debug1: permanently_set_uid: 0/0
debug1: identity file /root/.ssh/id_rsa type 1
debug1: identity file /root/.ssh/id_rsa-cert type -1
debug1: identity file /root/.ssh/id_dsa type -1
debug1: identity file /root/.ssh/id_dsa-cert type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_5.3
debug1: match: OpenSSH_5.3 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_5.3
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes256-ctr hmac-sha2-512 none
debug1: kex: client->server aes256-ctr hmac-sha2-512 none
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<4096<8192) sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
debug1: Host 'somehost' is known and matches the RSA host key.
debug1: Found key in /root/.ssh/known_hosts:203
debug1: ssh_rsa_verify: signature correct
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
|-----------------------------------------------------------------|
| This computer system and any networks that it may be connected  |
| to are for use only by authorised personnel. All use of this    |
| computer system and any attached devices or networks may be     |
| monitored or recorded for security purposes. Such monitoring    |
| may result in the acquisition, recording and analysis of all    |
| data being communicated, transmitted, processed or stored in    |
| this system by a user.  Use of this system is expressed consent |
| to such monitoring and recording.  Any unauthorized access or   |
| use of this system is prohibited and could be subject to legal  |
| and/or administrative action.                                   |
|-----------------------------------------------------------------|
debug1: Authentications that can continue: publickey,password
debug1: Next authentication method: publickey
debug1: Offering public key: /root/.ssh/id_rsa
debug1: Server accepts key: pkalg ssh-rsa blen 277
debug1: read PEM private key done: type RSA
debug1: Authentication succeeded (publickey).
debug1: channel 0: new [client-session]
debug1: Requesting no-more-sessions@openssh.com
debug1: Entering interactive session.
debug1: Sending environment.
debug1: Sending env LANG = en_US.UTF-8
<--- Hang point for close to an hour --->
debug1: channel 0: free: client-session, nchannels 1
Connection to somehost closed by remote host.
Transferred: sent 2304, received 3288 bytes, in 3600.1 seconds
Bytes per second: sent 0.6, received 0.9
debug1: Exit status -1

Without -vT it just says "Write failed: Broken pipe"

There is nothing in /var/log/secure other than the connection being allowed and the same in /var/log/messages.

SCP works as does ~~~"ssh somehost "some command here"~~~.