I don't know anything about Kolmogorov-Smirnov p-values, but I tend to believe that R is usually fairly efficient. So I would tend to think that if this is "extraordinarily slow," then it is probably not used correctly. Just my 2 cents.