turpialdev I've tested the command exactly as shown on several servers and the only place it seems to fail is on our single-CPU 2GB VPS servers.
I tried it a second time rendering a very simple "hello world" static page on your server and that worked fine.
I then tried google.com again on your server but with JS disabled, eg:
xvfb-run -a -s "-screen 0 640x480x16" wkhtmltopdf --disable-javascript http://google.com google.pdf
That ran very quickly and produced the expected output.
So, I suspect that wkhtmltopdf JS rendering is what's slowing things down.
Regarding the wkhtmltopdf version, we're using v0.12.4 here. It's always required a functioning X server, which is what xvfb-run is providing here. If you've been using wkhtmltopdf on a Linux desktop or a server with a functioning X server then you probably already have a working X server and would not need to run wkhtmltopdf via xvfb-run.