Yes, the idea about EXIF is very logical. You can try to forcefully use EXIF data via:

$image->orientate();

But check that the required php extension is installed

php -m | grep exif

if not, than

sudo apt-get install php-exif