Remove from array in WP_Query loop

This is happening because you are re-initializing the phrases array on each iteration. Define that array outside the loop and this code will work.

<?php

        $frontAgrs = array(
            'post_type' => 'page',
            'tag' => 'word',
            'order' => 'ASC'
        );

        $frontLoop = new WP_Query($frontAgrs);

/*----Phrase-------------*/ 
            $phrases = array('Hello Sailor','Acid Test','Bear Garden','Botch A Job','Dark Horse',
            'In The Red','Man Up','Pan Out','Quid Pro Quo','Rub It In','Turncoat',
            'Yes Man','All Wet','Bag Lady','Bean Feast','Big Wig');

        if($frontLoop->have_posts()):
            while($frontLoop->have_posts()):
                $frontLoop->the_post();

        $rand_Num = array_rand($phrases);
        $rand_phrase = $phrases[$rand_Num];
        unset($phrases[$rand_Num]);      
        echo count($phrases);       

    ?>

    <?php echo '<div><a href="'.get_permalink($post->ID).'"><p>'.$rand_phrase_value.'</p></a></div>' ?>


    <?php endwhile; endif; ?>

    <?php wp_reset_postdata(); ?>

Hope this solution works for you.

Edit:

See the working here.