What is the optimal way to create a recombined version of two lists?

I would do it like this

RandomChoice /@ Transpose[{l1, l2}]

In this case, Thread is more efficient than Transpose.

$HistoryLength = 0;

Clear["Global`*"]

Using longer lists to extend the timing.

l1 = CharacterRange["a", "z"] // ToExpression;

l2 = Range[Length[l1]];

With Table

SeedRandom[1234]

table = RepeatedTiming[
  Table[RandomChoice[{l1[[n]], l2[[n]]}], {n, Length[l1]}]]

(* {0.0000481, {1, 2, 3, d, e, f, g, h, i, 10, 11, l, 13, 14, o, 16, q, 18, 19, 
  t, 21, v, 23, x, y, z}} *)

With Transpose

SeedRandom[1234]

transpose = RepeatedTiming[RandomChoice /@ Transpose[{l1, l2}]]

(* {0.000026, {1, 2, 3, d, e, f, g, h, i, 10, 11, l, 13, n, o, 16, q, 18, 19, t, 
  21, v, 23, x, y, z}} *)

With Thread

SeedRandom[1234]

thread = RepeatedTiming[RandomChoice /@ Thread[{l1, l2}]]

(* {0.000019, {1, 2, 3, d, e, f, g, h, i, 10, 11, l, 13, n, o, 16, q, 18, 19, t, 
  21, v, 23, x, y, z}} *)

Comparing the timings:

(First /@ {table, transpose, thread})/table[[1]]

{1.00, 0.54, 0.39}