The continuous call to the lcd.clear() is causing the issue.
What you need to do is only check if the button is high or low when the button changes.
if (last_buttonState != buttonState)
{
last_buttonState = buttonState;
if (buttonState == HIGH)
{
lcd.clear();
lcd.print("Press button to get a random phrase.");
}
else if (buttonState == LOW) {
byte index = random(0, 4); //get a number between 0 and 4 :D
lcd.setCursor(0, 0);
lcd.clear();
lcd.print(phrases[index]); //use it as the index to the array of phrases
}
}
get it?