I am using ubuntu 12.04 and koha 3.8.7. I have about 1000-2000 books. My search about 2s. your problem is, maybe, large database, next ram is low (check it with free -m), then check %cpu is working! Make sure zebra is working ps aux | grep zebrasrv and is enabled in Koha! Best regards! Nguyen Quoc Uy