random() Function isn't random at all
You are correct, random() isn't random - it's pseudo random. It returns successive results from a mathematical formula which, to all intents and purposes, is random. It's also predictable, as you have seen.
The formula has a starting value, called the seed, which you can choose your self. Changing that seed gives you a different sequence of random-like numbers.
So the trick is to set the seed to something that is truly random. One common source of randomness, or entropy, is an unconnected ADC input:
randomSeed(analogRead(A3));

You can read more about the randomSeed() function here.