FWIW - It may be your base algorithms, not the PNRG you're using.
Just coded a quick & dirty test. It is not your rand() function. I used rand() drand48() and other PNRG's we have here. The number of iterations for all of them were all over the place, as you would expect. I used four fixed test arrays of six numbers.
I suspect it is your algorithm.
I create an array 1-47, select 6 of those at random(no duplicates) , copy them into an array with six elements, then compare the sorted small array with the original six element array.
This puts six random "choices" into the first six first six elements of arr[].
Code:
void shuffle(long arr[],int len)
{ /* len is always six */
int i;
int which=0;
for(i=0;i<len;++i) arr[i]=i+1;
for(i=0;i<6;++i)
{
which =rand()%len;
swap(&arr[which],&arr[i]);
}
}