So what should I be asking my vps provider? Is this some network issue?
Almost certainly "yes". If I had to guess I would think it was a DNS
timeout on something somewhere.
But unfortunately these system call traces are not very helpful. This
is because you are tracing the command "command", and all that shows is
you execute a nmh command and it waits 5 seconds for it to complete.
If this happens in the future you should probably use the -f option to
trace all children of the specified process/command, and the -t option
to print the system call timestamps (that would let you see exactly
where the delay is). I also like using -o to direct the trace output to
a file rather than having it mixed in with the output of a process.