Can't keep up! Is the server overloaded?

My server has been having a problem where if more than 2 people join, there's lag. At first it wasn't so bad, but when we tried to have 4 people today, it was awful. The console would say people moved too quickly and reset positions, and it was running 1,600 ticks behind at one point. Is this a problem on my side? How can I fix this?

Update: I killed some of my farm animals, and while it helped a bit, it's still about 100 ticks behind. This is a vanilla server on the latest version of Minecraft, and there's no plugins running. The server is Normal difficulty, so there's quite a few monsters.