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.