Randomizing list processing faster than Collections.shuffle()?

I am looking for: Either a faster way to shuffle than Java's Collections.shuffle() or an alternative method of processing the elements in an ArrayList in a randomized order.

It is important that the list is processed in a randomized order every time.

Currently, I have over 1,000,000 elements in the list I am trying to shuffle. Over time, this amount increases and it is becoming increasingly inefficient to shuffle it.

Is there an alternative data structure or way of randomizing the processing of elements that is faster?

I only need to use get and add. I have considered LinkedList and ArrayDeque but I haven't seen any performance improvements.

Here is some sample code to better explain what I am trying to achieve:

ArrayList<String> list = new ArrayList<>();
void process()
{
    list.add("hi");
    Random r = new Random();
    for (int i = 0; i < 100000; i++)
    {
        Collections.shuffle(list);//Something that will allow the order to be random (random quality does not matter to me), yet faster than a shuffle
        for (String str : list)
        {
            if(r.nextDouble() > 0.9)//10% chance of adding another string with twice the length of specified string
            {
                list.add(str + str);
            }
        }
    }
}