Si lo que quieres son todas las combinaciones posibles puedes usar el producto cartesiano de ambas listas usando [`itertools.product`](https://docs.python.org/2/library/itertools.html#itertools.product):

    >>> lista1 = ["R1", "R2", "R3", "R4", "R5", "R6"]
    >>> lista2 = ["Frase 1", "Frase 2", "Frase 3", "Frase 4", "Frase 5", "Frase 6"]
    >>> combinaciones = list(itertools.product(lista1, lista2))
    >>> len(combinaciones)
    36
    >>> combinaciones
    [('R1', 'Frase 1'),
     ('R1', 'Frase 2'),
     ('R1', 'Frase 3'),
     ('R1', 'Frase 4'),
     ('R1', 'Frase 5'),
     ('R1', 'Frase 6'),
     ('R2', 'Frase 1'),
     ('R2', 'Frase 2'),
     ('R2', 'Frase 3'),
     ('R2', 'Frase 4'),
     ('R2', 'Frase 5'),
     ('R2', 'Frase 6'),
     ('R3', 'Frase 1'),
     ('R3', 'Frase 2'),
     ('R3', 'Frase 3'),
     ('R3', 'Frase 4'),
     ('R3', 'Frase 5'),
     ('R3', 'Frase 6'),
     ('R4', 'Frase 1'),
     ('R4', 'Frase 2'),
     ('R4', 'Frase 3'),
     ('R4', 'Frase 4'),
     ('R4', 'Frase 5'),
     ('R4', 'Frase 6'),
     ('R5', 'Frase 1'),
     ('R5', 'Frase 2'),
     ('R5', 'Frase 3'),
     ('R5', 'Frase 4'),
     ('R5', 'Frase 5'),
     ('R5', 'Frase 6'),
     ('R6', 'Frase 1'),
     ('R6', 'Frase 2'),
     ('R6', 'Frase 3'),
     ('R6', 'Frase 4'),
     ('R6', 'Frase 5'),
     ('R6', 'Frase 6')]

Si quieres escoger una combinación al azaar puedes usar [`random.choice`](https://docs.python.org/2/library/random.html#random.choice):

    >>> import random
    >>> random.choice(combinaciones)
    ('R2', 'Frase 6')
    >>> random.choice(combinaciones)
    ('R6', 'Frase 4')
    >>> random.choice(combinaciones)
    ('R4', 'Frase 2')