Ubuntu server very slow out of the blue sky

I run Ubuntu server 8.04 with multiple Rails apps under Passenger + nginx. Today I've noticed it takes quite a lot of time to load a page (5-10 secs). And it's not only websites, ssh seems to be affected too.

Having no clue why this may be happening, I started to check different things. I checked how the log files are rotated, I checked if there's enough free disk space and memory. I also checked IO rate, here's the output:

$ iostat

avg-cpu:  %user   %nice %system %iowait  %steal   %idle
           0.17    0.00    0.02    0.57    0.16   99.07

Device:            tps   Blk_read/s   Blk_wrtn/s   Blk_read   Blk_wrtn
xvda              2.25        39.50        16.08     147042      59856
xvdb              0.00         0.05         0.00        192          0
xvdc              2.20        25.93        24.93      96530      92808
xvdd              0.01         0.12         0.00        434         16
xvde              0.04         0.23         0.35        858       1304
xvdf              0.37         0.31         4.12       1162      15352

Rebooting didn't help either. Any ideas where should I be looking?