I too am having the same problem.
Ubuntu VM running on a AM3+ FX 6300 Host. The VM has 2 cores allocated and 3GB ram. We mainly play locally over LAN
Its been running for several years now, running various versions as they come out. When we moved to 1.13, we created a new world, and then the lag started.
We see classic "rubber banding" lag, and the server states it is lagging behind.
I increased the VM allocation of virtual cores to all 6, it has had some effect but it is still very laggy. The server even stopped at one point today as the lag exceeded 60 seconds!
We've only had 3 players in this server at any one time so the specs should be perfectly suitable, but its not.
[14:17:15] [Server thread/WARN]: Can't keep up! Is the server overloaded? Running 12912ms or 258 ticks behind
[14:17:39] [Server thread/WARN]: Can't keep up! Is the server overloaded? Running 8954ms or 179 ticks behind
[14:17:59] [Server thread/WARN]: Can't keep up! Is the server overloaded? Running 5681ms or 113 ticks behind
[14:20:30] [Server thread/WARN]: Can't keep up! Is the server overloaded? Running 2006ms or 40 ticks behind
[14:21:00] [Server thread/WARN]: Can't keep up! Is the server overloaded? Running 15105ms or 302 ticks behind
[14:21:30] [Server thread/WARN]: Can't keep up! Is the server overloaded? Running 14950ms or 299 ticks behind
[14:21:55] [Server thread/WARN]: Can't keep up! Is the server overloaded? Running 10548ms or 210 ticks behind
[14:22:16] [Server thread/WARN]: Can't keep up! Is the server overloaded? Running 5708ms or 114 ticks behind
[14:22:35] [Server thread/WARN]: Can't keep up! Is the server overloaded? Running 4106ms or 82 ticks behind
I've found giving my server more memory has helped a lot. More of a workaround than a fix, but at least its playable.
Edit: Its a VM with two 3.52Ghz cores, and has 5Gb RAM assigned. This seems to support about 2-3 players before we see any noticeable lag
I start the server with the following switches:
-Xmx3G -Xms1024M