Shuffling many collections by folding over a numeric range
If you want to transform a value v by applying a function f n times, it may be clearer to use a combination of iterate and nth: 

(nth (iterate f v) n)


If you want to write a 'good' general-purpose implementation of shuffle that accepts a random generator, I suggest you simply adapt the implementation in clojure.core. You'll see the implementation you proposed is actually pretty close!

Regarding performance, keep in mind that if you want to shuffle a coll n times, nothing will beat the performance of repeatedly shuffling a mutable collection in place.