You say you "Need to Delete the server in $randomServer from @listOfServers and pick one randomly and try again." Are you sure? what if you empty your array of servers? Is this ok with what you have in mind?

edit: in case, you don't mind just going through your array once if all the servers are down, take a look at the two examples here:

#!/usr/bin/env perl
use strict;
use warnings;
use List::Util 'shuffle';
use feature 'say';

my $connectionStatus = "down";
my @listOfServers = ( "abc", "def", "lmn", "stu", "xyz" );

while (@listOfServers) {

    ##THIS:
    @listOfServers = shuffle @listOfServers;
    my $randomServer = shift @listOfServers;

    ##OR THIS, BUT NOT BOTH:
    my $randomServer = splice @listOfServers, rand @listOfServers, 1;

    my $connect = 0;
    say $randomServer;    # replace this with your connection test
    if ( $connect == 1 ) {
        $connectionStatus = "up";
        last;
    }
}
[download]