evaluation - How to inject an evaluated expression into a held expression?

I know that there are methods to structurally manipulate held expressions (discussed e.g. here), but I failed to apply those for this particular problem:

(Hold[{3, 4, 5 | 6}] /. (Verbatim@Alternatives)[x__] :> RandomChoice@List@x)

Hold[{3, 4, RandomChoice[{5, 6}]}]

The code should replace any Alternatives in the held expression with an appropriate choice from the alternatives, in this case either 5 or 6, i.e. it should evaluate the replacement.

Answer

Here are a couple of alternatives to Trott-Strzebonski in @R.M's answer:

Hold[{3,4,5|6}] /.
  Verbatim[Alternatives][x__] :> RuleCondition@RandomChoice@List@x

Hold[{3, 4, 5}]

Hold[{3,4,5|6}] /.
  Verbatim[Alternatives][x__] :> Block[{}, RandomChoice@List@x /; True]

Hold[{3, 4, 6}]

They operate on the same principle as Trott-Strzebonski (i.e. RuleCondition), but express the effect in different ways.