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 + 1) // 2 # Descontar los pares
                #   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`). Este chequeo puede hacerse para cada iteración del `for` interno; aunque reduce ligeramente el número de iteraciones, incrementa el tiempo de ejecución.
 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:

**Mejoras pendientes**
*En el cálculo de `potential_primes` hay que descontar todos los múltiplos de los factores primos en `factores`. Por el momento, sólo descuento los valores pares.*

Tiempo     : < 1 segundo

Iteraciones: 80.397 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
    0 s,  80397 iteraciones    

    Process finished with exit code 0