How can I get new random values with each blank in ReplaceAll?

You can simply change the Rule -> to RuleDelayed :> to give

{_, _, _} /. _Blank :> RandomInteger[{1, 10}]

(*{5, 1, 3}*)

Just for variety: you can also temporarily redefine Blank as RandomInteger[{1,10}]& using Block:

Block[{Blank = RandomInteger[{1, 10}] &}, {_, _, x, y, _, z}]

{5, 7, x, y, 5, z}