Try the following snippet for a Java 8 version:
// Generate random date
Random random = new Random();
LocalDate maxDate = LocalDate.of(2010, 1, 1);
long randomDay = random.nextInt((int) maxDate.toEpochDay());
LocalDate randomDate = LocalDate.ofEpochDay(randomDay);
// Convert to String using 'MMyy' pattern
DateTimeFormatter dtf = DateTimeFormatter.ofPattern("MMyy");
String result = dtf.format(randomDate.atStartOfDay());
System.out.println(result);
Note 1:
That should generate a random date between 1Jan1970 and 1Jan2010 (excluding) - is this what you wanted?
Note 2:
The date format is fixed and known a priori the way you stated it. So there is no need for the input string to "replace", just use result
(unless I misunderstood?)
Note 3:
See my answer to a more general (and possibly duplicate) question. You'll also find pre-Java 8 ideas there.