Java: Can't get "nice" random index numbers

I need a method that accepts an ArrayList of strings and uses that as a "source" from which to generate a new, randomly assembled, ArrayList of a specified length.
Actually, I need a few of those random ArrayLists results in each run!

My first approach:

public static ArrayList<String> mixFromInput (ArrayList<String> input, int outputLength) {
    ArrayList<String> result = new ArrayList<>();
    for (int i=0; i<outputLength; i++) {
        result.add(input.get(new Random().nextInt(input.size())));
    }
    return result;
}

However, this returns a suspicious "random" result (look at the last several iterations):

[Xy13005, Xy13003, Xy13004, Xy13005, Xy13003, Xy13006, Xy13000, Xy13004]
[Xy13004, Xy13004, Xy13004, Xy13003, Xy13006, Xy13006, Xy13005, Xy13004]
[Xy13003, Xy13005, Xy13006, Xy13006, Xy13004, Xy13004, Xy13006, Xy13005]
[Xy13004, Xy13005, Xy13006, Xy13005, Xy13006, Xy13006, Xy13005, Xy13006]
[Xy13005, Xy13005, Xy13006, Xy13006, Xy13005, Xy13006, Xy13004, Xy13006]
[Xy13005, Xy13005, Xy13004, Xy13005, Xy13005, Xy13004, Xy13005, Xy13005]
[Xy13004, Xy13005, Xy13005, Xy13005, Xy13005, Xy13005, Xy13005, Xy13005]
[Xy13005, Xy13004, Xy13004, Xy13005, Xy13005, Xy13005, Xy13005, Xy13005]
[Xy13004, Xy13004, Xy13005, Xy13005, Xy13004, Xy13005, Xy13005, Xy13005]
[Xy13005, Xy13004, Xy13004, Xy13005, Xy13005, Xy13004, Xy13004, Xy13004]

(Please ignore that these look like they are numbers. I am not looking to Xy+randomInt...)

The input to the above result is: Xy13000, Xy13001, Xy13002, Xy13003, Xy13004, Xy13005, Xy13006, Xy13007

I think my problem is that since Random() is using system time, and I am calling it using high performance code, it optimizes after a few iterations and the system time barely moves, yielding much less randomness than I expect - although, I could be wrong?

I thought that by creating a new Random() in each iteration of the result-assembly, it will help with "chaos" but this obviously doesn't work.

Things I tried, and got similar (undesirable) result:

• Moving Random() out of the loop
• Collections.shuffle(input); on each iteration
• Math.random()

Any ideas how to really shake things up here?

PS: Some code if you want to reproduce yourself:

    ArrayList<String> test = new ArrayList<>();
    test.add("Xy13000");
    test.add("Xy13001");
    test.add("Xy13002");
    test.add("Xy13003");
    test.add("Xy13004");
    test.add("Xy13005");
    test.add("Xy13006");
    test.add("Xy13007");
    for (int i=0; i<10; i++) {
        test = mixFromInput(test, unicodeKeyLength);
        System.out.println(test);
    }