Se você estiver em uma distribuição Linux onde o PHP a ser instalado por padrão é o 7.0+, então esse tutorial vai resolver seus problemas.

Lembrando que é necessário estar como super usuário para conseguir realizar as ações abaixo.

sudo su

Depois adicionar a dependência do PHP 5.6 e atualizar a lista de pacotes:

add-apt-repository ppa:ondrej/php
apt-get -y update

Então instalamos o Apache e MariaDB (esqueça o MySQL)

apt-get install -y apache2
apt-get install -y mariadb-server mariadb-client

Nesse ponto precisamos startar o MySQL

service mysql start
mysql_secure_installation

Então instalamos o PHP 5.6 e alguns pacotes essenciais:

apt-get install -y php5.6
apt-get install -y php5.6-mcrypt php5.6-mbstring php5.6-cli php5.6-mysql php5.6-gd php5.6-curl php5.6-intl php5.6-xsl php5.6-zip php5.6-soap
apt-get install -y curl libcurl3 libcurl3-dev

Vamos instalar também o PHPMyAdmin para facilitar nossa vida.

 apt-get install -y phpmyadmin 

Após isso realizamos algumas configurações básicas como habilitar o rewrite necessário para a URL amigável e o mCrypt, uma biblioteca que adiciona segurança (utilizado pelo Magento).

a2enmod rewrite
phpenmod mcrypt

E por fim reiniciamos o apache:

service apache2 restart

Fim.