Seeding with Random library Java yielding same results

My method for generating a Random Integer is done like so:

public static int randInt(int min, int max) {

    Random rand = new Random(System.currentTimeMillis());

    int randomNum = rand.nextInt((max - min) + 1) + min;

    return randomNum;
}

I am using this to choose random routes for the travelling salesman problem.

But for some odd reason it keeps finding the same route after ~5 seconds.

There is a small bit of variation but almost identical. Any idea why this is the case?

My guess is that in milliseconds just isn't precise enough. Should I go down to nanoseconds?