Esto es lo que he logrado. Creo que hay espacio para mejorar.

    import time
    import sympy
    
    def gensec(n: int, factores: list[int]):
        #   Función generadora que retorna la secuencia 1 a n
        #   excluyendo los múltiplos de los enteros de la
        #   lista de factores.
        indices = factores.copy()
        num_ind = len(indices)
        for valor in range(1, n):
            if valor in indices:
                #   Valor es múltiplo de alguno de los factores;
                #   descartarlo
                for i in range(num_ind):
                    #   Avanzar los indices para que todos sean
                    #   mayores que 'valor'.
                    if indices[i] == valor:
                        indices[i] += factores[i]
            else:
                yield valor
    
    preload_primes = 10_000_000
    primes_set = {i for i in range(3, preload_primes, 2) if sympy.isprime(i)}
    start = int(time.time())
    
    n = 10_000
    iteraciones = 0
    
    for i in range(3, n, 2):
        #   Determinar los factores primos de i
        factores = sympy.primefactors(i)
        primes = 0
        #   Recorrer los enteros de 1 a i saltando todos
        #   los múltiplos de los factores primos de i.
        for j in gensec(i, factores):
            iteraciones += 1
    
            k = j * j - j + i
    
            if k in primes_set or (k > preload_primes and sympy.isprime(k)):
                primes += 1
                #   ¿Cuantas iteraciones (y potenciales primos quedan)
                potential_primes = i - j
                #   Evaluar si podemos alcanzar tada > 0.5 en esta corrida
                if (primes + potential_primes) <= 0.5 * (i - 1):
                    #   No quedan suficientes primos para alcanzar tada > 0.5.
                    break
        tada = primes / (i - 1)
        if tada > 0.5:
            print(f"{i} {tada}")
    
    end = int(time.time())
    print(int(end-start), "s, ", iteraciones, "iteraciones")

Optimizaciones:

 1. Saltarse todos los pares en el `for` exterior.
 2. Precomputar los primos bajo 10 millones para no tener que evaluar `sympy.isprime()` una y otra vez para el mismo valor.
 3. Abandonar el `for` interior tan pronto quede claro que no llegamos al umbral requerido (`tada > 0.5`).
 4. En lugar de `range(1, i)` en el `for` interno, uso una función *generadora* `gensec(i, factores)` para saltar valores con factores primos comunes a 'i'.

La función generadora recibe la lista de factores primos de `i`. Al iterar, la función descarta todos los valores que sean múltiplos de algun factor, pues en ese caso, la expresión 

    k = j * j - j + i  

es divisible por al menos un factor primo, por lo que `k` no es primo.

Probando con `n = 10_000` y mi anciano tarro, obtengo estos resultados:

Tiempo     : 12 segundos

Iteraciones: 12.092.559 iteraciones


    3 1.0
    5 1.0
    7 0.6666666666666666
    11 1.0
    17 1.0
    41 1.0
    47 0.5652173913043478
    59 0.5862068965517241
    67 0.5454545454545454
    101 0.68
    107 0.6698113207547169
    161 0.50625
    221 0.5863636363636363
    227 0.584070796460177
    347 0.5057803468208093
    377 0.5079787234042553
    12 s,  12092559 iteraciones    

    Process finished with exit code 0