Tomar una lista con números en Python y cambiar sus valores sin repeticiones

tengo un array o lista en Python con 9 números (lista=[1,1,1,1,3,5,6,7,9]), necesito un código que tome esos números los recorra y que cuando encuentre uno repetido me genere aleatoriamente un nuevo numero para remplazarlo; la idea es que al final se arroje un nuevo array o lista con nueve números sin repetir.

Escribí este código tratando de controlar el valor del bucle con la variable j con el fin que no se salga del mismo hasta que no encuentre un valor aleatorio adecuado. ¿Qué me estará fallando? Agradezco su feedback.

import random

lista=[1,1,1,1,3,5,6,7,9]
      #0,1,2,3,4,5,6,7,8

for i in range(len(lista)):
    aux=i
    for j in range(1, len(lista)):
        
        if lista[j]==lista[i]:
            aleatorio=random.randint(0,9)
            if aleatorio not in lista:
                lista[i]=aleatorio
            else:
                aux=i
                j=j-1