Barrapunto

Y las ondas gravitacionales según tengo entendido viajan a la velocidad de la luz.

La paradoja EPR se llama así porque en su momento fué una paradoja (cuando la propusieron Einstein, Podolsky y Rosen para intentar demostrar que la teoría cuántica era incompleta), pero ahora se sabe que no hay tal paradoja.
En primer lugar: la información no viaja a mayor velocidad que la luz, ya que con un par de partículas en estado EPR es imposible enviar información sin previamente enviar algo de información clásica, y la información clásica deberá ser enviada por algún medio clásico el cual no podrá viajar a mayor velocidad que la luz.
El algoritmo cuántico de Teleportación de Bennett y otros [ibm.com] demuestra que para enviar la información contenida en un qubit utilizando justamente la paradoja EPR es necesario enviar 2 bits clásicos. Y si bien, al modificar el estado de una de esas partículas, la otra ha sufrido cambio instantáneamente, no se logra la "transmisión de la información" contenida en el qubit hasta que no se envíen los bits clásicos, y con eso se logra demuestra que no se puede enviar información a mayor velocidad que la luz.