Even commands like bitcoin-cli getbalance or getinfo take minutes to execute!

It's running on a 1GB ram VPS, with 4GB of swap. It's using most of the ram and 1GB of swap. It's a HDD vps, but nothing else is running on it but bitcoind.
So should be enough right?

Yet after running for several days it's becoming so slow I have to restart it. That fixes it for a while.
It's with the latest version for Ubuntu 14.04, all updated.