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

    import time
    import sympy
    
    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 = 1_000_000
    iteraciones = 0
    
    for i in range(3, n, 2):
        primes = 0
        for j in range(1, i):
            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) / (i - 1) <= 0.5:
                    #   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`).

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

Tiempo     : 12 segundos

Iteraciones: 14.725.596 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,  14725596 iteraciones
    
    Process finished with exit code 0