My random algoritm is not random. How to improve it?

I have a 64 character long string/array with dots on all positions when I start. I want to insert 6 characters from another string in their original order but at random position replacing the dot at that position.

Also, the first character of the short string always needs to be first in the long string (that is completely non-random). So for example, if the short string is ABCDEF and (just to simplify) the long string is 10 characters long these would be valid results:

A..B.CD.EF
AB.C..DEF.

I wrote a little Java for this purpose:

    StringBuilder base = new StringBuilder("................................................................");
    int positionPrevChar = 0;       
    base.setCharAt(0, prefix.charAt(0));        
    for (int i = 1; i < prefix.length(); i++) {
        int rnd = new Random().nextInt(64 - positionPrevChar - prefix.length() + i + 1);
        rnd = rnd + positionPrevChar; //You are not allowed to place the char before previous char.
        base.setCharAt(rnd, prefix.charAt(i));
        positionPrevChar = rnd;
    }
    System.out.println(base);

The result looks like this (100 tries)

a......b..................c.....d...........................ef..
a..............................................b......c......df.
a.b...............c.............................d......e..f.....
a..................b..........................c.........d.e..f..
a............................b.................c........def.....
a..b........................................................cdef
a.................................................b........cdf..
a..........................................b..........c...de..f.
a..........................................................e.f..
a............b..............c................................df.
a....b...........................cd.............ef..............
a.........................................b.................d.ef
a..........................................................bef..
a.......................................................c.d...f.
a........................b...c..e.......................f.......
a.........................b..........................c.d.....ef.
a.............b..................c.......d....e.............f...
a.........................................................b.ef..
a...............................................b........cd.e..f
a.........................................................b.cef.
a....................................b.......c......d.....e...f.
a.............................................b...........c..def
a........................................b.....d.............e.f
a..........................................b....c.....de...f....
a...b...............................c.................d.......f.
a..............................................b.........d....f.
a...........b.......................c.................d.....ef..
a.........b.......................c.......d..............e..f...
a.................................................b..c..d..e.f..
a...................b..................................c.d....f.
a..................................b...........c........de.....f
a................................b..............c..........df...
a.....................b...............................d..e.f....
a................................................b.......c...ef.
a................................c.............d....f...........
a..............................................b......c.d...f...
a......b..................c................................d.f..
a..................................................b..c....de..f
a.............b.........c................d...............e...f..
a................................b...........d...........f......
a.......................................b............cd..e.f....
a...................................b.......c............d....f.
a.........................................b.............c.d..e.f
a.......b......................cd..........................ef...
a.b................c...........d.........e..........f...........
a......................b...c.......d............e.f.............
a.................b............c............................def.
a.................b..............c.....................d..e.f...
a.................................................b.cd......ef..
a....b.............................................d......e.f...
a.......................................................b.c.de.f
a..........................................................bcdf.
a........................................................b..e.f.
a.b....................................................c..d..f..
a....................................b............cd..........f.
a........................................................b..cef.
a............................b..............c.......d...e...f...
a......................b.............................c.d...e..f.
a..............b..........................c.............d..e...f
a..................................................c.........def
a..............................................b...c.........e.f
a..........b.................................c.............d.f..
a................................b.....c.d..e..f................
a......................................................b...c.e.f
a................b.c......................e............f........
a..............................................b...........cde.f
a............................b............c.....e....f..........
a.....................................b................c..d...ef
a............................b...d...........................f..
a.b.......................c..d............ef....................
a......b....................................c.d......e......f...
a..........b........c...............d......................f....
a....................................................b....d.ef..
b...........................c................................f..
a............................................b.........c...e...f
a.........b..............................................cd...ef
a....................................................b.....d.ef.
a....................b......c.....d.e..f........................
a..b............c........................d.....e...........f....
a.bc..................................d.........e..........f....
a........................................................b..def.
a.............................................b..........c...def
a....................b............................c.........f...
a.b.................c.............................d...........ef
a...................................b..........c......d.e....f..
a......b..................................c....d.........e.f....
a................b.........c.......................d....f.......
a.......................b...........c..d....................e..f
a..........b............................c.......d.....e.......f.
a.........................................b........c..e....f....
a.......................................................b..c.def
a........b..........c...........d.........e............f........
a.b.......c...d.............e............................f......
a...........................................b.c.......d.......ef
a..................................b.............c......d..e...f
a.........................................b.........c........ef.
a......b.............c...............d..............e.........f.
a...................b......................................d..f.
a.....................................................c......ef.
a.............................................b...c........d.f..

The problem is obvious: this distribution is not random in the way I want it. The dots that are at the end of the original string are replaced with characters far more often than the dots at the beginning (with exception for the leftmost dot, but that is on purpose).

I also do understand the problem - when creating a random position for B, I pick among 64 - 5 positions (I can't place it to the right of 59 because then then rest of the string won't fit). Say that B gets position 20, then, for the next letter, C, there are only 44 - 4 positions left. And if C gets position 15 out of these 44, then it is only 29 - 3 positions left for D.

To sum up: the positions to the left are underused and the positions to the right are overused. I would like all the usage frequency of all positions (except 0) to be approximately equal. How do I adjust my algorithm to achieve that?