A "good enough" check is to see if the key starts with the correct header.
The data portion of the keyfile should decode from base64, or it will fail with a base64.binascii.Error
Unpack the first 4 bytes (an int), which should be 7. This is the
length of the following string (I guess this could be different, but you're only concerned with ssh-rsa).
openssh_pubkey = open('keyfile').read()
type, key_string, comment = openssh_pubkey.split()
data = base64.decodestring(key_string)
int_len = 4
str_len = struct.unpack('>I', data[:int_len])[0] # this should return 7
data[int_len:int_len+str_len] == type
Alternatively, you could forgo the binary checks, and look for AAAAB3NzaC1yc2EA
at the start of an ssh-rsa key, bit I would still verify it's valid base64.
[edit] Clarification:
Via the specification, the first part if the key is a length prefixed string. The length is packed as a big-endian unsigned int ('>I' for a python struct). It's a 7 here, because the following string, 'ssh-rsa', is 7 bytes long. data[4:11]
is the next 7 bytes (per the length prefix), but I edited the code above to use some descriptive variables to try and make this more clear. If you want to be thorough, you should also check for ssh-dss, and possibly pgp-sign-rsa, and pgp-sign-dss, but they are far less common.