How to check if an SSH private key has passphrase or not?

The keyfile will have a different header if it is password protected. Here's the top of a key without a passphrase:

-----BEGIN RSA PRIVATE KEY-----
MIIEogIBAAKCAQEA3qKD/4PAc6PMb1yCckTduFl5fA1OpURLR5Z+T4xY1JQt3eTM

And here's the top of a key which is passphrase-protected:

-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: DES-EDE3-CBC,556C1115CDA822F5

AHi/3++6PEIBv4kfpM57McyoSAAaT2ECxNOA5DRKxJQ9pr2D3aUeMBaBfWGrxd/Q

Unfortunately, that only works looking at the files. I know of no way for a server to be able to tell if the keys being presented to it were protected with a passphrase, which is the most useful place to be able to leverage that sort of info.

It is not always so easy as described in the other answers. It works only with the old PEM keys. New openssh format of the keys (generated with -o option, more secure, since openssh-6.5) looks the same if you check the headers:

$ head rsa_enc
-----BEGIN OPENSSH PRIVATE KEY-----
b3BlbnNzaC1rZXktdjEAAAAACmFlczI1Ni1jYmMAAAAGYmNyeXB0AAAAGAAAABCYdi7MhY
$ head rsa
-----BEGIN OPENSSH PRIVATE KEY-----
b3BlbnNzaC1rZXktdjEAAAAABG5vbmUAAAAEbm9uZQAAAAAAAAABAAABFwAAAAdzc2gtcn

The easiest way in this case is to run some operation on them using ssh-keygen. If it will ask for a passphrase, it has one (or it is not a ssh key), if not it does not have a passphrase:

$ ssh-keygen -yf rsa_enc
Enter passphrase: 
$ ssh-keygen -yf rsa
ssh-rsa AAAAB3NzaC1y...

Maybe even better is the following example, since it doesn't ask for input: -P specifies the passphrase to use, an unprotected key opens with an empty passphrase.

$ ssh-keygen -y -P "" -f rsa_enc
Load key "path_to_key": incorrect passphrase supplied to decrypt private key`
$ ssh-keygen -y -P "" -f rsa
ssh-rsa AAAAB3NzaC1y...

The "RSA key" is actually a set of values stored as an ASN.1 structure in the standardized DER binary format, then encoded in base-64 to get the final PEM file.

A very easy way to determine whether a key is encoded or not is simply to check whether the ASN.1 header is present, and this is usually as simple as checking if the "key" begins with the letters MII as in the example below:

-----BEGIN RSA PRIVATE KEY-----
MIICWwIBAAKBgQCWxk9djtgA/t7n6M8g1d2fk3exyCSu1uubpxUkoFLJBKjLYiaa
[...]
eCrpRFHxhPICHI4db+I8GZ9QDmlbCN/bl3BBNNTn3w==
-----END RSA PRIVATE KEY-----

In password protected files, the whole ASN.1 structure being encrypted, it all appears as random characters.