Unable to connect to server with ssh2_connect

I'm using the following commands:

$connection = ssh2_connect('IP_ADDRESS', 22);
ssh2_auth_password($connection, 'user', 'pass');
echo ssh2_exec($connection, 'ls');

And I get this error:

PHP Warning:  ssh2_connect(): Error starting up SSH connection(-5): Unable to exchange encryption keys

On the remote server I see the following:

Unable to negotiate with IP_ADDRESS port xxx: no matching host key type found. Their offer: ssh-rsa,ssh-dss [preauth]

I can't really figure out what the problem is. This is the first time I'm trying to use ssh2_connect to connect to a remote server.