Replacing a part of a string with a randomly generated number

I have a string that looks something like that

my_string='TAG="0000" TAG="1111" TAG="2222"'

what I want to do is simply replace those numbers by randomly generated ones in my string.

I was consindering doing something like:

new_string = my_string.replace('0000',str(random.randint(1,1000000)))

This is very easy and it works. Now let's say I want to make it more dynamic (in case I have a very long string with many TAG elements), I want to tell the code: "Each time you find "TAG=" in my_string, replace the following number with a random one". Does anyone have an idea?

Thanks a lot.