That depends on your actual application. If you need exactly some number of lines and the distribution must be uniform then your current approach of generating an index file in some fashion seems appropriate. If that file is sorted then you can open both the index file and the data file at the same time, read the 'next' index from the index file and read lines from the data file until you reach the index, repeat until you reach the end of the index file. Consider:

use warnings;
use strict;

open my $rndLines, '<', "rand_sorted.txt" or die "Can't open rand_sort
+ed.txt: $!";

while (defined (my $nextLine = <$rndLines>)) {
    chomp $nextLine;
    
    next unless $nextLine =~ /^\d+/;
    
    my $line;
    while (defined ($line = <>)) {
        last if $. >= $nextLine;
    }
    
    print $line if defined $line;
}

close $rndLines;
[download]

A presume the rand () < 0.5 and print while <>; approximate number of lines solution I gave earlier doesn't do what you need?