Debian Configuration :: Timeouts And Dependency Failures On Boot - Crypto Related

I've got this weird problem: when I reboot my Debian 8.3 server, I have to run through the crypto unlocking processes for my encrypted volumes a few times before I actually get to a login screen. The operation times out 85% of the time, leaving me to reboot and try over and over until the system is happy.

Here's my partitioning setup (manually partitioned at install):
/boot: 500 MB, EXT2, nodev, nosuid, noexec
/tmp: 2 GB, EXT2, AES-256/xts-plain64 with RANDOM KEY
swap: 2.5 GB, AES-256/xts-plain 64 with RANDOM KEY
/: 35 GB, EXT4, AES-256/xts-plain 64 with PASSPHRASE
/var: 35 GB, EXT4, AES-256/xts-plain 64 with PASSPHRASE
/home: 45 GB, EXT4, AES-256/xts-plain 64 with PASSPHRASE

Here's the output from journalctl -b -p 3:
Code: Select allDate and time | server name | systemd[1]: Timed out waiting for device dev-sda5.device
Date and time | server name | systemd[1]: Dependency failed for Cryptography Setup for sda5_crypt
Date and time | server name | systemd[1]: Dependency failed for Encrypted Volumes
Date and time | server name | systemd[1]: Dependency failed for dev-mapper-sda5_crypt.device
Date and time | server name | systemd[1]: Dependency failed for /tmp

[Code] ....

I had the same problem in previous builds where I chose Twofish instead of AES, and I was hoping that the timeouts would be fixed by switching to AES as my CPU has the AES instruction set. Obviously that didn't make a damn bit of difference.

What am I doing wrong, or what should I change in my setup? The encryption is a requirement. Could the problem be caused by something as stupid as using a RANDOM KEY instead of a PASSPHRASE on /tmp and swap?

Debian 8.3 as OS version.